Code Festival 2015 予選B D - マスと駒と色塗り/Squares, Pieces and Coloring

問題

白いマスが横一列に無限個並んでいる
クエリがn個与えられ、i番目のクエリでは以下の操作を行った後に駒が置かれている位置を出力する
1) マスa[i]に駒を置き、カウンタを0に初期化する
2) 駒のあるマスが白ならそのマスを黒に塗ってカウンタを1増加させ、マスが黒なら1つ右のマスに駒を移動させる
3) 2を繰り返し、カウンタの値がb[i]になったら操作終了
1 <= n <= 10^5
1 <= a, b <= 10^9

解法

setでゴリ押しで通らんかな？と思ったら通った上に想定解だった
正確な最悪計算量が見積もれないんだけど、区間の数が大量にあるときはその状態になるまでに大量のクエリが二分探索一回で終わってるってことだし、区間のマージが大量に行われるときはその1回は割と重いけどその後区間が一気に減るからしばらく軽くなるし、TLEするほど重くなることはないやろとは思った
解説pdfではO(nlogn)て書いてる
少なくとも俺の実装はO(nlogn)には見えないけど・・

実装

黒く塗ったマスの区間をsetに入れて、区間がかぶるたびにマージしていく方針

マスaからb個ってことでとりあえず[a, a+b-1]を塗ろうとする (以下a+b-1をbとする)
→ aが既存の区間の内側にある場合はマージして、左端aを既存の区間の左端にし、右端bをかぶってる区間の長さだけ右にずらす
→ かぶってる区間を見つける度にマージして右端をその区間の長さだけ右にずらすことを続ける

#define int long long

int n, a, b;
set<pair<int,int> > s;

signed main() {
	cin >> n;
	while (n--) {
		cin >> a >> b;
		b = a+b-1;
		if (s.empty()) {
			s.insert({a,b});
			cout << b << endl;
			continue;
		}
		// 左端がどっかに含まれてるかチェック
		pair<int,int> t = {a,linf};
		auto it = s.upper_bound(t);
		if (it!=s.begin()) it--;
		if (it->fi <= a && a <= it->se) {
			int mv = it->se - a + 1;
			a = it->fi, b += mv;
			s.erase(it);
		}
		// マージしながら右端を右に動かしていく
		while (1) {
			t = {a,0};
			it = s.lower_bound(t);
			if (it==s.end() || b < it->fi) break;
			b += it->se - it->fi + 1;
			s.erase(it);
		}
		cout << b << endl;
		s.insert({a,b});
	}
}