2023wangzhaolan @ 2024-05-28 19:07:49
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
struct cmp{
int c,q;
bool operator<(const cmp &b)const{return (q==b.q)?(c<b.c):(q>b.q);}
}a[N];
int n,m,v[N];
int ans[N];
struct FHQ_treap{
int pcnt=0,root=0;
struct node{
int ls,rs,rd,id,v,ans,lz,la;
}t[N];
/* void outtree(int p){
if(!p)return ;
push_down(p);
cout<<p<<":v "<<t[p].v<<",son "<<t[p].ls<<" "<<t[p].rs<<",id "<<t[p].id<<",ans "<<t[p].ans<<"\n";
outtree(t[p].ls);outtree(t[p].rs);
}*/
void push_down(int p){
if(t[p].lz){
if(t[p].ls){
t[t[p].ls].lz+=t[p].lz;
t[t[p].ls].v-=t[p].lz;
}
if(t[p].rs){
t[t[p].rs].lz+=t[p].lz;
t[t[p].rs].v-=t[p].lz;
}
t[p].lz=0;
}
if(t[p].la){
if(t[p].ls){
t[t[p].ls].la+=t[p].la;
t[t[p].ls].ans+=t[p].la;
}
if(t[p].rs){
t[t[p].rs].la+=t[p].la;
t[t[p].rs].ans+=t[p].la;
}
t[p].la=0;
}
}
void Split(int &L,int &R,int p,int x){
if(!p)return L=R=0,void();
push_down(p);
if(t[p].v<=x){L=p;Split(t[L].rs,R,t[p].rs,x);}
else{R=p;Split(L,t[R].ls,t[p].ls,x);}
}
int merge(const int &a,const int &b){
if(!a||!b)return a|b;
push_down(a);push_down(b);
if(t[a].rd>t[b].rd){t[a].rs=merge(t[a].rs,b);return a;}
else{t[b].ls=merge(a,t[b].ls);return b;}
}
void insert(const int &x,const int &id){
int p=++pcnt;t[p].v=x;t[p].id=id;t[p].rd=rand();
int l,r;Split(l,r,root,x);
root=merge(l,merge(p,r));
}
void erase(const int &x){
int a,b,c;
Split(a,b,root,x-1);t[b].lz+=x;t[b].v-=x;t[b].la+=1;t[b].ans+=1;Split(b,c,b,x-1);
int l,r;
while(b){
push_down(b);
int u=b;
b=merge(t[b].ls,t[b].rs);
t[u].ls=t[u].rs=0;
Split(l,r,a,t[u].v);
a=merge(l,merge(u,r));
}
root=merge(a,c);
}
void delete_(int p){
if(!p)return ;push_down(p);ans[t[p].id]=t[p].ans;delete_(t[p].ls);delete_(t[p].rs);
}
}s;
signed main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].c,&a[i].q);
sort(a+1,a+n+1);
cin>>m;
for(int i=1;i<=m;i++)scanf("%lld",&v[i]);
for(int i=1;i<=m;i++){s.insert(v[i],i);}
for(int i=1;i<=n;i++){
s.erase(a[i].c);
}
s.delete_(s.root);
for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
return 0;
}//by 20130709aaa @ 2024-05-28 19:14:50
#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=200010;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,m;
struct Node { int c,q; }a[N]; int b[N];
inline bool cp(Node x,Node y) { return x.q==y.q?x.c<y.c:x.q>y.q; }
int root,ch[N][2],siz[N],rnd[N],val[N],sum[N],t1[N],t2[N];
inline int New_Node(int x,int k) { val[k]=x, siz[k]=1, rnd[k]=rand(); return k; }
inline void Push_Up(int x) { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; }
inline void Push_Down(int x)
{
if(ch[x][0]) t1[ch[x][0]]+=t1[x], t2[ch[x][0]]+=t2[x], val[ch[x][0]]-=t1[x], sum[ch[x][0]]+=t2[x];
if(ch[x][1]) t1[ch[x][1]]+=t1[x], t2[ch[x][1]]+=t2[x], val[ch[x][1]]-=t1[x], sum[ch[x][1]]+=t2[x];
t1[x]=t2[x]=0;
}
void Split(int root,int k,int &x,int &y)
{
if(!root) { x=y=0; return; }
Push_Down(root);
if(val[root]<=k) x=root, Split(ch[root][1],k,ch[root][1],y);
else y=root, Split(ch[root][0],k,x,ch[root][0]);
Push_Up(root);
}
int Merge(int x,int y)
{
if(!x||!y) return x|y;
Push_Down(x), Push_Down(y);
if(rnd[x]<rnd[y]) { ch[x][1]=Merge(ch[x][1],y), Push_Up(x); return x; }
else { ch[y][0]=Merge(x,ch[y][0]), Push_Up(y); return y; }
}
inline void Insert(int k,int ui)
{
int x,y;
Split(root,k,x,y);
root=Merge(Merge(x,New_Node(k,ui)),y);
}
void Change(int x,int &to,int C)
{
Push_Down(x);
if(ch[x][0]) Change(ch[x][0],to,C);
if(ch[x][1]) Change(ch[x][1],to,C);
ch[x][0]=ch[x][1]=0;
int y,z;
val[x]-=C, sum[x]++;
Split(to,val[x],y,z);
to=Merge(Merge(y,x),z);
}
inline void UpDate(int C)
{
int x,y,z;
Split(root,C-1,x,y);
Split(y,C*2-1,y,z);
if(z) val[z]-=C, t1[z]+=C, sum[z]++, t2[z]++;
Change(y,x,C);
root=Merge(x,z);
}
void Down(int x)
{
Push_Down(x);
if(ch[x][0]) Down(ch[x][0]);
if(ch[x][1]) Down(ch[x][1]);
}
signed main()
{
srand(time(NULL));
n=read();
for(ri int i=1;i<=n;i++) a[i].c=read(), a[i].q=read();
sort(a+1,a+1+n,cp);
m=read();
for(ri int i=1;i<=m;i++) b[i]=read(), Insert(b[i],i);
for(ri int i=1;i<=n;i++) UpDate(a[i].c);
Down(root);
for(ri int i=1;i<=m;i++) printf("%d ",sum[i]);
puts("");
return 0;
}