Typical DP Contest K - ターゲット

問題

n個の円があり、それぞれの中心はx軸上にある。
i番目の円の中心はxi, 半径はriである。


円の列C1, C2, ..., Cnは、円Ci+1がCiの真に内部に入っているときにターゲットであると言う。作れるターゲットの最大のサイズを求めよ。

制約条件

n≦100000

方針

円を右端が大きい順にならべる。
で、左端の最長増加部分列を求めればよい。


n年前の自分はbinary indexed treeを使いよくわからないことをしたようだ。

ソースコード

const int MX = 100010;
int bit[MX];
inline int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res = max(res, bit[i]);
	return res;
}
inline void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] = max(bit[i], x);
}
 
int n;
vector<pi> in;
vi xs;
 
int main(){
	cin >> n;
	rep(i, n){
		int x, r;
		cin >> x >> r;
		in.pb(mp(-x - r, x - r));
		xs.pb(x - r);
	}
	sort(all(xs));
	sort(all(in));
	
	for(int i = 0; i < n; ){
		vi v;
		
		for(int j = i; j < n && in[i].first == in[j].first; j++){
			
			int x = lower_bound(all(xs), in[j].second) - xs.begin();
			v.pb(sum(x) + 1);
		}
		rep(j, v.size()){
			
			int x = lower_bound(all(xs), in[i++].second) - xs.begin() + 1;
			add(x, v[j]);
		}
	}
	cout << sum(n + 5) << endl;
	
	return 0;
}

残り解説書いてない問題はG, L, M, N, S.
解いたの大分前だしほとんど忘れている…