Codeforces 198(#125 Div1) E. Gripping Story

問題

座標平面上の(x, y)に宇宙船が固定されている。
最初、自分から距離r以下にある質量p以下の物体を回収できるマジックハンドをもっている。

宇宙空間にはn個のマジックハンドが散らばっており、
i番目のマジックハンドは座標(xi, yi)にあって、質量がmiであり、距離ri以下にある質量pi以下の物体を回収できる。
最初から持っているおよび回収したマジックハンドは、宇宙船から何度でも使うことができる。

最大でいくつのマジックハンドを回収できるか求めよ。

制約条件

n≦250000
座標とか質量とか≦10^9

方針

座標は関係ないので、全部宇宙船からの距離にしてしまってよい。
距離およびマジックハンドのパワーを座標圧縮する。

すると、マジックハンドは(距離, 質量)の二次元平面上の一点になる。
x座標を距離, y座標を質量で取る。
性能が(X, Y)のマジックハンドを回収すると、距離質量が(x, y)でx≦X, y≦Yなマジックハンドを全て回収できることになる。

回収したマジックハンドの性能が(X', Y')であるときに、別のマジックハンド(X, Y)で
X'≦X, Y'≦Yなものがあったら、前者のマジックハンドは完全に不要。
なので、マジックハンドはX座標の昇順に並べると、Y座標は減少列になる。
なのでこれを平衡二分木で管理する。

新たにマジックハンドを回収したとき、このギザギザの形を更新するのであるが、
平面上の点のうち、ギザギザが変わった部分の図形を、長方形に縦に区切って、それぞれの長方形にあるものだけを見てやるようにする。
長方形内部の点クエリは、range treeを使えばできる。

クエリが呼ばれる回数は、ギザギザがどれくらい更新されるかであるが、
一つのマジックハンドでギザギザの角は新たに高々3つしか増えない。
で、増えた角は高々1度しか減らないので、O(n)回しかこの長方形のクエリは来ないことになる。
range treeなので、一回の長方形のクエリはO(m + log^2n)（mは取り出す点の個数）で、
取り出せる点の個数は合計でn個しかなくて、全ての点は一度しか取り出されないので、
計算量はO(nlog^2n)になる。

なので、長方形の部分を全部処理して間に合う。

ソースコード

const int N = 250000;
int X, Y, P, R, n;
int x[N], y[N], m[N], d[N], p[N], r[N];

const int M = 1048576;
vector<pi> dat[2 * M - 1];

inline void query(int a, int b, int k, int l, int r, int lb, int ub, vi &v){
	if(b <= l || a >= r) return;
	if(a <= l && r <= b){
		int i = lower_bound(all(dat[k]), mp(lb, 0)) - dat[k].begin();
		int j = lower_bound(all(dat[k]), mp(ub + 1, 0)) - dat[k].begin();
		while(i < j) v.pb(dat[k][i++].second);
		return;
	}
	int m = (l + r) / 2;
	query(a, b, k * 2 + 1, l, m, lb, ub, v);
	query(a, b, k * 2 + 2, m, r, lb, ub, v);
}
inline vi query(int a, int b, int lb, int ub){//[a, b) x [lb, ub)の点を全て報告
	vi res;
	query(a, b, 0, 0, M, lb, ub, res);
	return res;
}

#define F first
#define S second

int ans;
set<pi> pts;
bool can[N];

void calc(int dist, int power){
	
	set<pi>::iterator it = pts.lower_bound(mp(dist, power));
	if(it != pts.end() && it->S >= power) return;
	
	pi dp(dist, power);
	vector<pi> er;
	vi vs;
	
	while(1){
		int y = it == pts.end() ? 0 : it->S;
		
		if(it != pts.begin()){
			--it;
			vi v = query(it->F, dist, y, power);
			vs.insert(vs.end(), all(v));
			if(it->S <= power){
				dist = it->F;
				er.pb(*it);
			}
			else break;
		}
		else{
			vi v = query(0, dist, y, power);
			vs.insert(vs.end(), all(v));
			break;
		}
	}
	each(i, er) pts.erase(*i);
	pts.insert(dp);
	each(i, vs) if(!can[*i]){
		ans++;
		can[*i] = 1;
		calc(r[*i] + 1, p[*i] + 1); //回収したマジックハンドで連鎖的に回収
	}
}

int main(){
	scanf("%d%d%d%d%d", &X, &Y, &P, &R, &n);
	vector<ll> ds;
	ds.pb((ll)R * R);
	
	rep(i, n){
		scanf("%d%d%d%d%d", x + i, y + i, m + i, p + i, r + i);
		x[i] -= X; y[i] -= Y;
		ds.pb((ll)x[i] * x[i] + (ll)y[i] * y[i]);
		ds.pb((ll)r[i] * r[i]);
	}
	sort(all(ds));
	ds.erase(unique(all(ds)), ds.end());
	R = lower_bound(all(ds), (ll)R * R) - ds.begin();
	
	rep(i, n){
		r[i] = lower_bound(all(ds), (ll)r[i] * r[i]) - ds.begin();
		d[i] = lower_bound(all(ds), (ll)x[i] * x[i] + (ll)y[i] * y[i]) - ds.begin();
		dat[d[i] + M - 1].pb(mp(m[i], i));
	}
	for(int i = M - 2; i >= 0; i--){
		int l = i * 2 + 1, r = i * 2 + 2;
		dat[i].resize(dat[l].size() + dat[r].size());
		merge(all(dat[l]), all(dat[r]), dat[i].begin());
	}
	
	calc(R + 1, P + 1);
	printf("%d\n", ans);
	
	return 0;
}