TopCoder SRM 794 : Div1 Medium FloodFill

しょうもないミスでげんなり。
https://community.topcoder.com/stat?c=problem_statement&pm=16668&rd=18405

問題

無限に広がる二次元のグリッドにおいて、N個のセルにある水源の位置が与えられる。
各水源は時間に応じて水を排出し、時間tだけ立った後には、X座標とY座標がいずれも水源からt以内にあるセルが水で満たされる。

各セルを、水で満たされる時間順に並べたとする。
また、同じ時間に満たされたセル群は、座標順に並べられたとする。

この列でK番目に来るセルはどこか。

解法

まずK番目のセルが現れる時刻を求める。
f(t) := 時刻tまでに満たされるセルの総数
とするとf(t)は単調増加なので二分探索を行えばよく、二分探索の各ステップでは座標圧縮と平面走査を使えば、複数の正方形が占める領域の和集合を求めることができる。

次に、時刻tが求まったら時刻tで新たに水で満たされたセルのうちK-f(t-1)番目を求めよう。
時刻tで新たに水で満たされたセルは、複数の正方形の外周から、他の正方形の内部になるセルを除いたものとなる。
そこでやはり座標圧縮と平面走査をしていくとよい。

int N;
vector<int> X,Y;

class FloodFill {
	public:
	ll num(ll v) {
		vector<ll> ys;
		int i;
		vector<pair<int,int>> ev;
		FOR(i,N) {
			ys.push_back(Y[i]-v);
			ys.push_back(Y[i]+v+1);
			ev.push_back({X[i]-v,i});
			ev.push_back({X[i]+v+1,i+N});
		}
		sort(ALL(ys));
		ys.erase(unique(ALL(ys)),ys.end());
		int D[30],U[30];
		FOR(i,N) {
			D[i]=lower_bound(ALL(ys),Y[i]-v)-ys.begin();
			U[i]=lower_bound(ALL(ys),Y[i]+v+1)-ys.begin();
		}
		
		int bt[66]={};
		ll sum=0;
		sort(ALL(ev));
		int px=-1<<29;
		FORR(e,ev) {
			ll ysum=0;
			int i;
			FOR(i,ys.size()-1) if(bt[i]) ysum+=ys[i+1]-ys[i];
			sum+=ysum*(e.first-px);
			px=e.first;
			if(e.second<N) {
				for(i=D[e.second];i<U[e.second];i++) bt[i]++;
			}
			else {
				for(i=D[e.second-N];i<U[e.second-N];i++) bt[i]--;
			}
		}
		return sum;
	}
	
	vector<int> get(ll v,ll A) {
		vector<ll> ys;
		int i;
		map<int,vector<int>> ev;
		FOR(i,N) {
			ys.push_back(Y[i]-v);
			ys.push_back(Y[i]-v+1);
			ys.push_back(Y[i]+v);
			ys.push_back(Y[i]+v+1);
			ev[X[i]-v].push_back(i);
			ev[X[i]+v].push_back(i+N);
		}
		sort(ALL(ys));
		ys.erase(unique(ALL(ys)),ys.end());
		int D[30],U[30];
		FOR(i,N) {
			D[i]=lower_bound(ALL(ys),Y[i]-v)-ys.begin();
			U[i]=lower_bound(ALL(ys),Y[i]+v+1)-ys.begin();
		}
		
		int bt[140]={};
		ll sum=0;
		int px=-1<<29;
		FORR(e,ev) {
			ll ysum=0;
			int i;
			FOR(i,ys.size()-1) if(bt[i]>0&&bt[i]<100) ysum+=ys[i+1]-ys[i];
			
			if(A<=ysum*(e.first-px)) {
				int cx=px;
				if(A%ysum==0) {
					cx+=A/ysum-1;
					A=ysum;
				}
				else {
					cx+=A/ysum;
					A%=ysum;
				}
				FOR(i,ys.size()-1) if(bt[i]>0&&bt[i]<100) {
					if(--A==0) return {cx,(int)ys[i]};
				}
			}
			A-=ysum*(e.first-px);
			
			FORR(v,e.second) {
				
				if(v<N) {
					for(i=D[v];i<U[v];i++) bt[i]++;
				}
				else {
					for(i=D[v-N]+1;i<U[v-N]-1;i++) bt[i]-=99;
				}
			}
			FOR(i,ys.size()-1) if(bt[i]>0&&bt[i]<100) {
				if(ys[i+1]-ys[i]>=A) {
					return {e.first,ys[i]+A-1};
				}
				else {
					A-=ys[i+1]-ys[i];
				}
			}
			px=e.first+1;
			FORR(v,e.second) {
				
				if(v<N) {
					for(i=D[v]+1;i<U[v]-1;i++) bt[i]+=99;
				}
				else {
					for(i=D[v-N];i<U[v-N];i++) bt[i]--;
				}
			}
		}
		cout<<A<<endl;
		assert(0);
		return {0,0};
	}
	
	vector <int> getCell(vector <int> X, vector <int> Y, long long A) {
		::X=X;
		::Y=Y;
		N=X.size();
		ll tim=1<<28;
		int i;
		for(i=27;i>=0;i--) if(num(tim-(1<<i))>=N+A) tim-=1<<i;
		cout<<tim<<" "<<num(tim)<<" "<<num(tim-1)<<endl;
		A=A+N-num(tim-1);
		
		return get(tim,A);
		
	}
}

まとめ

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