続いてG。
これ、以前なら部分点しか解けなかった問題なので、今回解き切れてよかった。
http://wupc2nd.contest.atcoder.jp/tasks/wupc_07
初期ブロック数が10万、クエリが10万。
この問題は、ブロックの検索と追加を行う必要があるけど、データ構造を配列にしてもリストにしても、検索と追加のどちらかはO(N)になる。
そのため、ストレートに実装すると、クエリと合わせてO(N^2)となってしまい時間切れとなる。
周りはBit Index Tree派と平方分割派がいたようだけど、自分はBITがいまいち苦手なので平方分割で挑んだ。
ブロック1000個ずつまとめると、大体O(N^1.5)になるので何とか解ける。
ブロックの削除は面倒なので、今回は削除したブロックは高さが0として扱った。
あとは最上段のブロックについては、ハンマーが上にはみ出ても良い点に注意して素直に書けばよい。
サンプルで上にはみ出るケースがあったので、おかげで1発でAC取れた。
ll N,M,H; ll hei[2001],th; vector<int> blocks[2002]; void solve() { int x,y,i,j,rr,TM,nc; int tx,ty; char cmd[100]; ll p,cch; N=GETi(); M=GETi(); H=GETi(); ZERO(hei); th=0; FOR(i,N){ p=GETi(); blocks[i/1000].push_back(p); hei[i/1000]+=p; th+=p; } FOR(rr,M) { GETs(cmd); p=GETi(); if(strcmp(cmd,"add")==0){ N++; blocks[N/1000].push_back(p); hei[N/1000]+=p; th+=p; } else { cch=th; p-=H; FOR(i,2001) { if(p>=hei[i]) { p-=hei[i]; cch-=hei[i]; } else { ll ch=0; FOR(j,blocks[i].size()) { if(p<ch+blocks[i][j]) { if(p+2*H<=ch+blocks[i][j] || ch+blocks[i][j]==cch) { hei[i]-=blocks[i][j]; th-=blocks[i][j]; blocks[i][j]=0; _P("go\n"); } else { _P("stop\n"); } goto out; } else { ch+=blocks[i][j]; } } _P("miss\n"); goto out; } } _P("miss\n"); out: ; } } return; }
まとめ
N=10^5程度の場合、O(N^1.5)かO(N logN)を狙うのがいいね。