Codeforces ECR #003 : F. Frogs and mosquitoes

面倒だけどやるだけと言えばやるだけ。
http://codeforces.com/contest/609/problem/F

問題

N匹の蛙が数直線上にいる。
それぞれX[i]の位置にいて、右方向に下をT[i]まで伸ばせる。

ここにM匹の蚊が順に落ちてくる。その位置はP[i]で大きさはB[i]である。
蚊の落ちた位置に蛙の舌が到達できない場合、蚊はそこに居続ける。

蚊の落ちた位置にいずれかの蛙の舌が到達可能な場合、一番X[i]の小さい蛙がその蚊を食べる。
蚊を食べた蛙はB[i]だけ舌を伸ばせる距離T[i]が増加する。
また、その結果新たに居続ける蚊に到達可能ならば、その分蚊を食べ続ける。

最終的に各蛙が食べた蚊の数と最終的なT[i]の値を求めよ。

解法

setを使い、蛙のカバーする座標の範囲と、居続ける蚊の位置を管理しよう。
まず蚊が落ちてきたら、そのP[i]をカバーする蛙の存在をチェックする。
存在しなければ蚊はその場所に居続ける。

存在する場合、蛙はその蚊を食べる。
その蛙は舌の到達範囲が広がるので、居続ける蚊を含むかどうか判定しよう。

int N,M;
ll X[202020],T[202020],C[202020];
ll P[202020],B[202020];
pair<int,int> F[202020];
set<pair<ll,int> > S;
set<pair<ll,int> > rem;

void extend(int x,int v) {
	S.erase({X[x]+T[x],x});
	while(1) {
		auto it=S.lower_bound({X[x]+T[x],0});
		if(it==S.end() || it->first>X[x]+T[x]+v) break;
		S.erase(it);
	}
	T[x]+=v;
	C[x]++;
	S.insert({X[x]+T[x],x});
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>X[i]>>T[i], F[i]={X[i],i};
	FOR(i,M) cin>>P[i]>>B[i];
	
	sort(F,F+N);
	FOR(i,N) {
		x=F[i].second;
		if(S.empty() || S.rbegin()->first<X[x]+T[x]) S.insert({X[x]+T[x],x});
	}
	
	FOR(i,M) {
		cin>>P[i]>>B[i];
		auto it = S.lower_bound({P[i],0});
		if(it!=S.end() && X[it->second]<=P[i]) {
			x=it->second;
			extend(x,B[i]);
			
			while(1) {
				auto rit=rem.lower_bound({X[x],0});
				if(rit==rem.end() || rit->first>X[x]+T[x]) break;
				extend(x,B[rit->second]);
				rem.erase(rit);
			}
		}
		else {
			rem.insert({P[i],i});
		}
	}
	FOR(i,N) cout<<C[i]<<" "<<T[i]<<endl;
	
}

まとめ

実装は面倒だけど、やることはストレートだよね。