Codeforces #310 Div1 C. Case of Chocolate

本番散々はまったけど、わかってしまえばあっさり。
http://codeforces.com/contest/555/problem/C

問題

N*Nの２次元グリッドがある。
初期状態で各セルは無色である。

ここでQ個のクエリが与えられる。
各クエリはセルの位置(x,y)と塗りつぶし方向(左か上)が与えられる。
クエリのセルから、指定された方向に１マスずつセルを塗りつぶしていく。
途中グリッドの外周に到達するか、すでに塗られたセルに到達したら塗りつぶしを終了する。

各クエリで塗りつぶされるセルの数を求めよ。

解法

EditorialではSegTreeと書いてあるし、本番自分もSegTreeがうまく作れず失敗。

もっと簡単な方法で解かれていたので、ここではそれを解説。
既に処理を終えたクエリのX座標に対し、塗った方向及び塗ったマス数のペアをsetで管理する。
初期状態では外周の代わりにX=0で上向き、X=N+1で左向きに0マス塗られている、という情報をsetに入れておくと良い。

クエリの塗る向きが左向きの場合を考える。
Xに対して、set中でXより小さい最大のX座標をX'とする。

• X'で左向きに塗っているのであれば、Xではその時の塗りつぶしマス数+(X-X')マスを塗りつぶせる。
• X'で上向きに塗っているのであれば、Xでは(X-X')マスを塗りつぶせる。

上に塗る場合も同様にXより大きい最小ののX座標X'を求めて処理すればよい。

ll N;
int Q;
map<int,pair<char,int> > M;
int X,Y;
char D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	M[0]={'U',0};
	M[N+1]={'L',0};
	
	while(Q--) {
		cin>>X>>Y>>D;
		
		if(M.count(X)) {
			_P("0\n");
			continue;
		}
		
		auto it=M.lower_bound(X);
		if(D=='L') it--, x=X-it->first;
		else x=it->first-X;
		if(D==it->second.first) x+=it->second.second;
		
		_P("%d\n",x);
		M[X]={D,x};
	}
}

まとめ

散々SegTreeをバグらせたあとにこの解法みたので、目からうろこでした。