Codeforces ECR #028 : D. Monitor

この回は普通に全完。
http://codeforces.com/contest/846/problem/D

問題

N*Mのグリッドがある。
一部のマスはある時間に利用不可能になる。
K*Kの正方形領域全体が利用不可能になるような場所が現れる最短時間を求めよ。

解法

時間がわかれば累積和の要領でO(NM)でK*K領域の存在を判定できるので、時間で二分探索すればよい。

int H,W,K,Q;
vector<vector<int>> V;
int mat[505][505];

int broken(int t) {
	if(t+1<K*K) return 0;
	
	ZERO(mat);
	int i;
	FOR(i,t+1) mat[V[i][1]][V[i][2]]=1;
	int y,x;
	FOR(y,H) {
		for(x=W-1;x>=0;x--) if(mat[y][x]) mat[y][x]+=mat[y][x+1];
		FOR(x,W) mat[y][x]=mat[y][x]>=K;
	}
	FOR(x,W) {
		for(y=H-1;y>=0;y--) if(mat[y][x]) {
			mat[y][x]+=mat[y+1][x];
			if(mat[y][x]>=K) return 1;
		}
	}
	return 0;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K>>Q;
	FOR(i,Q) {
		cin>>y>>x>>r;
		V.push_back({r,y-1,x-1});
	}
	sort(ALL(V));
	
	int tim=Q-1;
	if(broken(tim)==0) return _P("-1\n");
	for(i=20;i>=0;i--) if(broken(tim-(1<<i))) tim-=1<<i;
	cout<<V[tim][0]<<endl;
	
}

まとめ

ここら辺はすんなり。