Codeforces #810 : Div1 B. Rain

良くもなく悪くもなく。
https://codeforces.com/contest/1710/problem/B

問題

N回雨が降った。
i回目の雨では、座標X[i]を中心に、強さP[i]の雨が降った。
この時、位置xではmax(0,P[i]-(X[i]-x))だけ水が溜まる。
もしMより多くの水が溜まる位置が1か所でもあれば、洪水が発生する。

N回のうち1回だけ雨が降らなかった場合、それぞれ洪水が起きるかどうか答えよ。

解法

座標圧縮したうえで、累積和を使い各地点で振る雨の量をAx+Bのように座標xの一次関数で表現しよう。
そのうえで、各雨が降った場所について、その雨がなければ水の量がMを超えないかチェックすればよい。

int T;
int N,M;
int X[202020],P[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> btm,bts;

vector<int> cand[606060];
int ok[606060];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		vector<ll> Xs;
		Xs.push_back(-(1LL<<30));
		Xs.push_back((3LL<<30));
		
		FOR(i,N) {
			cin>>X[i]>>P[i];
			Xs.push_back(X[i]);
			Xs.push_back(X[i]-P[i]);
			Xs.push_back(X[i]+P[i]);
			ok[i]=1;
		}
		sort(ALL(Xs));
		Xs.erase(unique(ALL(Xs)),Xs.end());
		FOR(i,Xs.size()) cand[i].clear();
		
		FOR(i,N) {
			int a,b,c;
			a=lower_bound(ALL(Xs),X[i]-P[i])-Xs.begin();
			b=lower_bound(ALL(Xs),X[i])-Xs.begin();
			c=lower_bound(ALL(Xs),X[i]+P[i])-Xs.begin();
			cand[b].push_back(i);
			btm.add(a,1);
			bts.add(a,-(X[i]-P[i]));
			btm.add(b,-2);
			bts.add(b,(X[i]-P[i]));
			bts.add(b,(X[i]+P[i]));
			btm.add(c,1);
			bts.add(c,-(X[i]+P[i]));
		}
		ll cur=-1LL<<60;
		FOR(i,Xs.size()) {
			ll v=btm(i)*Xs[i]+bts(i);
			if(v>M) {
				cur=max(cur,v-M-Xs[i]);
			}
			FORR(e,cand[i]) {
				if(P[e]<cur+X[e]) ok[e]=0;
			}
		}
		cur=-1LL<<60;
		for(i=Xs.size()-1;i>=0;i--) {
			ll v=btm(i)*Xs[i]+bts(i);
			if(v>M) {
				cur=max(cur,v-M+Xs[i]);
			}
			FORR(e,cand[i]) {
				if(P[e]<cur-X[e]) ok[e]=0;
			}
		}
		FOR(i,N) {
			int a,b,c;
			a=lower_bound(ALL(Xs),X[i]-P[i])-Xs.begin();
			b=lower_bound(ALL(Xs),X[i])-Xs.begin();
			c=lower_bound(ALL(Xs),X[i]+P[i])-Xs.begin();
			cand[b].push_back(i);
			btm.add(a,-1);
			bts.add(a,(X[i]-P[i]));
			btm.add(b,2);
			bts.add(b,-(X[i]-P[i]));
			bts.add(b,-(X[i]+P[i]));
			btm.add(c,-1);
			bts.add(c,(X[i]+P[i]));
			cout<<ok[i];
		}
		cout<<endl;
		
	}
}

まとめ

もっと短く書けないかな…。