文件详细信息

下载本文件

本文件的大小为 2808 字节。

#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<ctime>
void read(int&num){
	num=0;
	int ch=getchar();
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
void write(int a){
	static int ch[20],cnt;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	cnt=0;
	while(a)ch[++cnt]=a%10|48,a/=10;
	while(cnt)putchar(ch[cnt--]);
}
int abs(int a){
	return a>=0?a:-a;
}
int random(){
	return abs((rand()<<15)^rand());
}
const int maxn=200005;
int n,k,tot;
struct Node{
	Node*ch[2];
	int key,pri,size,sum,tag,minus;
}T[maxn];
Node*rt=T;
void pushup(Node*u){
	u->size=u->ch[0]->size+u->ch[1]->size+1;
}
void pushdown(Node*u){
	if(u->tag){
		if(u->ch[0]!=T&&u->ch[0]){
			u->ch[0]->sum+=u->tag;
			u->ch[0]->tag+=u->tag;
		}
		if(u->ch[1]!=T&&u->ch[1]){
			u->ch[1]->sum+=u->tag;
			u->ch[1]->tag+=u->tag;
		}
		u->tag=0;
	}
	if(u->minus){
		if(u->ch[0]!=T&&u->ch[0]){
			u->ch[0]->minus+=u->minus;
			u->ch[0]->key-=u->minus;
		}
		if(u->ch[1]!=T&&u->ch[1]){
			u->ch[1]->minus+=u->minus;
			u->ch[1]->key-=u->minus;
		}
		u->minus=0;
	}
}
Node*merge(Node*x,Node*y){
	if(x==T)return y;
	if(y==T)return x;
	pushdown(x);
	pushup(x);
	pushdown(y);
	pushup(y);
	if(x->pri<y->pri){
		x->ch[1]=merge(x->ch[1],y);
		pushup(x);
		return x;
	}else{
		y->ch[0]=merge(x,y->ch[0]);
		pushup(y);
		return y;
	}
}
void split(Node*u,int k,Node*&x,Node*&y){
	if(u==T){
		x=y=T;
		return;
	}
	pushdown(u);
	if(u->key<=k){
		x=u;
		split(u->ch[1],k,u->ch[1],y);
	}else{
		y=u;
		split(u->ch[0],k,x,u->ch[0]);
	}
	pushup(u);
}
Node*newnode(int val){
	Node*u=T+(++tot);
	(*u)=Node{{T,T},val,random(),1,0,0,0};
	return u;
}
void pushdown_all(Node*u){
	if(u==T)return;
	pushdown(u);
	pushdown_all(u->ch[0]);
	pushdown_all(u->ch[1]);
}
struct Input{
	int c,q;
}in[maxn];
bool operator<(const Input a,const Input b){
	return a.q!=b.q?a.q>b.q:a.c<b.c;
}
Node*Q[maxn];
int front,tail;
int main(){
	srand(time(0));
	read(n);
	for(int i=1;i<=n;i++)read(in[i].c),read(in[i].q);
	std::stable_sort(in+1,in+n+1);
	read(k);
	int temp;
	T->ch[0]=T->ch[1]=T;
	Node*x,*y,*z,*a,*b;
	for(int i=1;i<=k;i++){
		read(temp);
		split(rt,temp,x,y);
		rt=merge(merge(x,newnode(temp)),y);
	}
	for(int i=1;i<=n;i++){
		split(rt,in[i].c-1,x,y);
		split(y,(in[i].c<<1)-1,y,z);
		z->minus+=in[i].c;
		z->key-=in[i].c;
		z->tag++;
		z->sum++;
		front=1,tail=0;
		Q[++tail]=y;
		while(front<=tail){
			Node*t=Q[front++];
			pushdown(t);
			if(t->ch[0]!=T&&t->ch[0])Q[++tail]=t->ch[0];
			if(t->ch[1]!=T&&t->ch[1])Q[++tail]=t->ch[1];
			split(x,t->key-in[i].c,a,b);
			t->ch[0]=t->ch[1]=T;
			t->key-=in[i].c;
			t->size=1;
			t->tag=0;
			t->sum++;
			t->minus=0;
			x=merge(merge(a,t),b);
		}
		rt=merge(x,z);
	}
	pushdown_all(rt);
	for(int i=1;i<=k;i++)write(T[i].sum),putchar(i!=k?' ':'\n');
	return 0;
}