Codeforces 219(#135 Div2 only) E. Parking Lot

問題

横一列にn台の駐車スペースがあり、左から順に1, ..., nと名前がついている。
ここにm個の車の到着または出発のクエリが来るので処理せよ。
車は以下のアルゴリズムで駐車場所を選ぶ。

全ての空きスペースの中で、一番近くにある他の車までの距離が最大になる場所を選ぶ。
複数ある場合、その中で最も番号が小さい場所を選ぶ。
駐車場が空のときは1番の場所を選ぶ。

制約条件

n, m≦2*10^5
車のid番号は10^6以下の数
車が止まれない状態で駐車のクエリが来ることはない
止まっていない車の発車のクエリが来ることはない

方針

区間を平衡二分木で管理する。
区間(a, b)があるとき、ここに車が止まるなら、(a + b) / 2の位置に止まる。

平衡二分木を二つもち、
一つは(次に車が止まったときの最寄の車の位置, 区間の左端)
もう一つは(区間の左端, 区間の右端)をそれぞれ管理する。

次に車止まる位置を探したいときは、前者の平衡二分木の最初の要素をとればよいが、両端にある駐車スペースだけは例外なので、個別に処理する。
車が発車したときは、区間(x, x + 1)を追加するのだが、このとき隣接する区間とマージする処理を書く。

ソースコード

もうちょいマシな実装できないものか…

int n, q, pos[10000010];

struct S{
	set<pi> iv, len;
	inline int find(){
		#if 0
		each(i, iv) cerr<<i->first<<", "<<i->second<<"  "; cerr<<endl;
		each(i, len) cerr<<i->first<<", "<<i->second<<"  "; cerr<<endl;
		#endif
		pi mx(1, 0);
		if(iv.begin()->first == 0){
			mx = min(mx, mp(iv.begin()->first - iv.begin()->second + 1, 0));
		}
		set<pi>::iterator it = iv.end(); --it;
		if(it->second == n) mx = min(mx, mp(it->first - it->second + 1, n - 1));
		
		int b = -len.begin()->first, a = len.begin()->second;
		mx = min(mx, mp(-b, a + b));
		
		return mx.second;
	}
	inline void del(int a, int b){
		iv.erase(mp(a, b));
		len.erase(mp(-(b - a - 1) / 2, a));
	}
	inline void del(int x){
		set<pi>::iterator it = iv.lower_bound(mp(x + 1, 0));
		--it;
		int a = it->first, b = it->second;
		del(a, b);
		if(a < x) ins(a, x);
		if(x + 1 < b) ins(x + 1, b);
	}
	inline void ins(int a, int b){
		iv.insert(mp(a, b));
		len.insert(mp(-(b - a - 1) / 2, a));
		fix(a, b);
	}
	inline void fix(int a, int b){
		set<pi>::iterator it = iv.lower_bound(mp(a, b));
		if(it != iv.end() && ++it != iv.end() && it->first == b){
			
			int c = it->second;
			del(a, b); del(b, c); ins(a, c);
		}
		else{
			it = iv.lower_bound(mp(a, b));
			if(it != iv.begin() && (--it)->second == a){
				
				int c = it->first;
				del(c, a); del(a, b); ins(c, b);
			}
		}
	}
};

int main(){
	scanf("%d%d", &n, &q);
	S s;
	s.ins(0, n);
	
	while(q--){
		int t, id; scanf("%d%d", &t, &id);
		if(t == 1){
			pos[id] = s.find();
			printf("%d\n", pos[id] + 1);
			s.del(pos[id]);
		}
		else{
			s.ins(pos[id], pos[id] + 1);
		}
	}
	return 0;
}