2012 WUPC2 : G - だるま落とし

続いて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として扱った。
あとは最上段のブロックについては、ハンマーが上にはみ出ても良い点に注意して素直に書けばよい。
サンプルで上にはみ出るケースがあったので、おかげで１発で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)を狙うのがいいね。