#include #include typedef long long int int64; typedef struct RMQandRAQ{ int64 *add; int64 *max; int size,bit; } segTree; segTree* newRMQandRAQ(const int n){ int k=0; while((1<add=(int64 *)calloc(2*size,sizeof(int64)); s->max=(int64 *)calloc(2*size,sizeof(int64)); s->size=size; s->bit=k; return s; } inline int64 max(int64 a,int64 b){ return a>b?a:b; } inline int64 calcMax(segTree *s,int k){ return s->add[k]+s->max[k]; } void propagate(segTree *s,int k){ if(s->add[k]==0) return; s->add[2*k ]+=s->add[k]; s->add[2*k+1]+=s->add[k]; s->add[k]=0; s->max[k]=max(calcMax(s,2*k),calcMax(s,2*k+1)); return; } void add(segTree *s,int l,int r,int64 v){ l+=s->size; r+=s->size-1; for(int i=s->bit;i>0;i--){ propagate(s,l>>i); propagate(s,r>>i); } for(int x=l,y=r+1;x>=1,y>>=1){ if(x&1) s->add[x++]+=v; if(y&1) s->add[--y]+=v; } l>>=1; r>>=1; while(l>=1){ s->max[l]=max(calcMax(s,2*l),calcMax(s,2*l+1)); s->max[r]=max(calcMax(s,2*r),calcMax(s,2*r+1)); l>>=1; r>>=1; } } int search(segTree *s,int64 h){ typedef struct { int l,r,k; } range; range stack[32]; int top=0; stack[top++]=(range){0,s->size,1}; int res=0; while(top>0){ const range t=stack[--top]; if(calcMax(s,t.k)=s->size){ res++; add(s,t.l,t.l+1,-1000000000000000LL); continue; } propagate(s,t.k); int m=(t.l+t.r)/2; stack[top++]=(range){t.l,m,2*t.k}; stack[top++]=(range){m,t.r,2*t.k+1}; } return res; } void run(void){ int n,w; int64 h; scanf("%d%d%lld",&n,&w,&h); segTree *s=newRMQandRAQ(w); int cnt[2]={0,0}; int i; for(i=0;icnt[1]?"A":"B"); } int main(void){ run(); return 0; }