Codeforces #312 Div2 D. Guess Your Way Out! II

2250ptになってるけど、Cよりこっちの方が簡単だと思う。本番ミスったけど。
http://codeforces.com/contest/558/problem/D

問題

高さHの完全二分木が与えられる。

各頂点には番号が振ってある。
根の番号は1であり、またi番の頂点の子は左から2*i,2*i+1となる。

葉の頂点2^(H-1)～2^H-1のいずれか１つを当たりとする。
ここでQ個のクエリが与えられる。
各クエリは同じ高さにある頂点番号の区間を指しており、その頂点の子孫に当たり頂点があるかどうかを示している。

この木に対して、当たり頂点はどういう状態にあるか答えよ。

• 当たり候補が１つに絞れるならそれを答えよ。
• 当たり候補が２つ以上あって絞れないなら、情報不足と答えよ。
• 条件を満たすような当たり候補が存在しないなら、反則と答えよ。

解法

各クエリの区間から、対応する葉の区間が求まる。
求めるあたり頂点は、

• 「区間に含む」ような全クエリの共通部分に含まれ
• 「区間に含まない」ような全クエリの和集合に含まれない

というものを求めなければならない。

まず前者のクエリを処理しよう。
区間の共通部分を求めていくので、最終的に得られるのは１つの区間となる。
この得られた区間の中で、『「区間に含まない」ような全クエリの和集合」に含まれない最小及び最大の番号を求める。

• 最小の番号＝最大の番号なら、当たりは１つに絞れたことになる。
• 最小の番号＜最大の番号なら、当たりは２つ以上ある。
• 最小の番号＞最大の番号なら、当たりはない。

int H,Q;
ll CL,CR;
vector<pair<ll,ll>> O,O2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>Q;
	CL=0,CR=1LL<<(H-1);
	ll L,R;
	
	while(Q--) {
		cin>>x>>L>>R>>y;
		L -= 1LL<<(x-1);
		L <<= H-x;
		
		R++;
		R -= 1LL<<(x-1);
		R <<= H-x;
		
		if(y==1) {
			CL=max(L,CL);
			CR=min(R,CR);
		}
		else {
			O.emplace_back(L,R);
			O2.emplace_back(R,L);
		}
	}
	
	sort(ALL(O));
	sort(ALL(O2));
	reverse(ALL(O2));
	FORR(r,O) if(r.first<=CL && CL<r.second) CL=r.second;
	FORR(r,O2) if(r.second<CR && CR<=r.first) CR=r.second;
	
	if(CL+1<CR) return _P("Data not sufficient!\n");
	if(CL>=CR) return _P("Game cheated!\n");
	cout << CL + (1LL<<(H-1)) << endl;
}

まとめ

境界条件ミスしてもったいなかった。