2011 Apples
みんなこの問題を動的にStarry Sky木を組んでやるとか言ってますが、そんなに動的っぽくは無いと思います。とはいってもこんな特殊なSegmentTreeはじめて書いた。配列からついに逸脱した。あと、mapを使って逃げることに成功しました。
map
というものをついに覚えました。iteratorは++や--ならできるらしい。
定数倍怖かったけど余裕で通っていた。
#include<stdio.h> #include<algorithm> #include<map> using namespace std; struct wolf{ int left; int right; int val; int par; wolf(int t){ left=right=-1; val=0; par=t; } wolf(){} }; wolf segtree[5000000]; int del[100000]; int at; void add(unsigned int a,unsigned int b,int c,int d,int e,int f){ if(d<a||b<c)return; if(c<=a&&b<=d){ segtree[e].val+=f; }else{ if(segtree[e].left==-1){ segtree[e].left=at; segtree[at++]=wolf(e); } if(segtree[e].right==-1){ segtree[e].right=at; segtree[at++]=wolf(e); } add(a,(a+b)/2,c,d,segtree[e].left,f); add((a+b)/2+1,b,c,d,segtree[e].right,f); } if(e){ int s=segtree[e].par; if(~segtree[s].left&&~segtree[s].right){ if(segtree[segtree[s].left].val>0||segtree[segtree[s].right].val>0||(segtree[segtree[s].left].val<0&&segtree[segtree[s].right].val<0)){ int q=max(segtree[segtree[s].left].val,segtree[segtree[s].right].val); segtree[s].val+=q; segtree[segtree[s].left].val-=q; segtree[segtree[s].right].val-=q; } } else if(~segtree[s].left){ segtree[s].val+=segtree[segtree[s].left].val; segtree[segtree[s].left]=0; } else if(~segtree[s].right){ segtree[s].val+=segtree[segtree[s].right].val; segtree[segtree[s].right]=0; } } } int query(int a){ if(segtree[0].val<a)return -1; int now=0; unsigned left=0; unsigned right=2147483647; int v=segtree[0].val; while(left<right){ if(~segtree[now].right&&v+segtree[segtree[now].right].val>=a){ left=(left+right)/2+1; v+=segtree[segtree[now].right].val; now=segtree[now].right; }else{ right=(left+right)/2; v+=segtree[segtree[now].left].val; now=segtree[now].left; } } return (int)left; } char in[2]; map<int,int>M; int main(){ int a,b; scanf("%d%d",&a,&b); segtree[at++]=wolf(-1); M[2147483647]=1; for(int i=0;i<a;i++){ scanf("%s",in); int c; if(in[0]=='A'){ scanf("%d",&c); if(M.count(c))M[c]=M[c]+1; else M[c]=1; add(0,2147483647,c,c+b,0,1); // printf("%d\n",S.size()); }else if(in[0]=='R'){ scanf("%d",&c); int P=query(c); if(P==-1){ printf("NO\n"); fflush(stdout); }else{ //P-=b; map<int,int>::iterator m=M.upper_bound(P); m--; // printf("%d\n",P); int L=0; for(int j=0;j<c;j++){ del[j]=(*m).first; if(!L)L=(*m).second; add(0,2147483647,del[j],del[j]+b,0,-1); L--; if(!L)m--; } for(int j=0;j<c;j++){ if(j)printf(" "); printf("%d",del[c-1-j]); } for(int j=0;j<c;j++){ M[del[j]]=M[del[j]]-1; if(M[del[j]]==0)M.erase(del[j]); } printf("\n"); fflush(stdout); // printf("%d\n",M.size()); } }else return 0; } }
ところで皆さんBeltといていてぱないと思います。1日に2回も幾何するほど気力がなかった。