WUPC2nd G - だるま落とし

問題

日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_07）

次のようなクエリm個に答える。
高さhのだるまを、一番上に重ねる。
高さyの場所をハンマーで叩く。

このとき、ハンマーがあたらないならmiss,
複数のだるまに当たるならstop,
ひとつだけのだるまに当たるなら、そのだるまを取り除き、goを出力する。

制約条件

n, m≦100000
h≦100000
y≦10^12

方針

適当に平方分割したら通った。
クエリを√n回やるごとに、バケットを再構築する。

バケットごとに合計の高さをもっておくと、探索がO(√n)でできて、
だるまの追加はO(1), 削除はO(√n)でできる。

当たるだるまを見つけるには、だるまの上端がハンマーの下端を超えるまで、
次のだるまを見ていけばよい。

想定解はbinary indexed tree + 二分探索らしい。

ソースコード

const int SZ = 400;
int n, q, x;
int a[200000];
vector<pair<ll, vi> > block;
 
void init(){
	n = 0;
	rep(i, block.size()) rep(j, block[i].second.size()) 
	a[n++] = block[i].second[j];
}
void rebuild(){
	block.clear();
	vi v;
	ll s = 0;
	rep(i, n){
		s += a[i];
		v.pb(a[i]);
		if(v.size() == SZ){
			block.pb(mp(s, v));
			s = 0;
			v.clear();
		}
	}
	if(v.size()) block.pb(mp(s, v));
}
 
int main(){
	cin >> n >> q >> x;
	
	rep(i, n) cin >> a[i];
	rebuild();
	
	rep(it, q){
		string op;
		ll y;
		cin >> op >> y;
		if(op[0] == 'a'){
			if(block.back().second.size() >= SZ){
				block.pb(mp(0, vi(0)));
			}
			block.back().second.pb(y);
			block.back().first += y;
		}
		else{
			ll h = 0;
			int i, j;
			for(i = 0; i < (int)block.size(); i++){
				if(h + block[i].first > y - x) break;
				h += block[i].first;
			}
			if(i == (int)block.size()){
				cout << "miss" << endl;
				continue;
			}
			
			for(j = 0; j < (int)block[i].second.size(); j++){
				if(h + block[i].second[j] > y - x) break;
				h += block[i].second[j];
			}
			if(i == (int)block.size() - 1 && j >= (int)block[i].second.size() - 1){
			}
			else if(!(h <= y - x && y + x <= h + block[i].second[j])){
				cout << "stop" << endl;
				continue;
			}
			
			cout << "go" << endl;
			ll tmp = block[i].second[j];
			block[i].second.erase(block[i].second.begin() + j);
			block[i].first -= tmp;
			
			if(it % SZ == SZ - 1) init(), rebuild();
		}
	}
	return 0;
}