[Codeforces] 198E. Gripping Story

題目連結:http://codeforces.com/contest/198/problem/E

---

被雷了才會QQ
會發現其實他是個圓並不重要，重要的其實是距離，所以不妨把每個人的座標轉換成跟原點的距離，這樣的話每次詢問就變成詢問一個距離內質量小於k的數有誰，而我們其實也不用一次把一坨東西拉出來，只要一次拉一個就好，反正最多拉n個，複雜度不會太慘。而這樣其實就是詢問一個前綴極值就可達到這件事，所以就開個BIT套個單調的queue之類的就可以做到這件事了。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
#define ALL(x) begin(x), end(x)
#define FF first
#define SS second
const int N = 250000 + 5;
const lld INF = 1LL<<31;

class LiSan{
	private:
		vector<lld> vv;
	public:
		inline void init(){vv.clear();}
		inline void insert(lld x){vv.PB(x);}
		inline void done(){
			sort(ALL(vv));
			vv.resize(distance(vv.begin(), unique(ALL(vv))));
		}
		inline int size(){return vv.size();}
		inline int get(lld x){
			return distance(vv.begin(), lower_bound(ALL(vv), x));
		}
		inline lld inv_get(int x){return vv[x];}
} lisan;

struct Obj{
	lld d, m, p, r;
	bool operator<(const Obj &x) const {
		return tie(m, d) < tie(x.m, x.d);
	}
} arr[N];

class BIT{
	typedef pair<Obj, int> node;
	private:
		bool removed[N];
		queue<node> nodes[2*N];
		int n;
		inline int lowbit(int x){return x&(-x);}
	public:
		void init(int _n){
			n=_n;
			memset(removed, 0, sizeof(removed));
			fill(nodes, nodes+n, queue<node>());
		}
		void add(int p, node x){
			while(p<n){
				nodes[p].push(x);
				p+=lowbit(p);
			}
		}
		node query(int x){
			node ret = {{INF, INF, INF, INF}, INF};
			while(x){
				while(!nodes[x].empty() and removed[nodes[x].front().SS])
					nodes[x].pop();
				if(!nodes[x].empty()) ret = min(ret, nodes[x].front());
				x-=lowbit(x);
			}
			return ret;
		}
		void erase(int id){
			removed[id]=1;
		}
} bit;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	lisan.init();
	lld x, y, p, r, n; cin>>x>>y>>p>>r>>n;
	lisan.insert(0); lisan.insert(r*r);
	for(int i=0;i<n;i++){
		lld xx, yy; cin>>xx>>yy;
		cin>>arr[i].m>>arr[i].p>>arr[i].r;
		xx-=x, yy-=y;
		arr[i].d = xx*xx+yy*yy;
		arr[i].r*=arr[i].r;
		lisan.insert(arr[i].d);
		lisan.insert(arr[i].r);
	}
	lisan.done();
	bit.init(lisan.size()+3);
	sort(arr, arr+n);
	for(int i=0;i<n;i++) bit.add(lisan.get(arr[i].d), {arr[i], i});
	int ans = 0;
	queue<Obj> qq;
	qq.push({0, 0, p, r*r});
	while(!qq.empty()){
		auto cur = qq.front(); qq.pop();
		lld dd = lisan.get(cur.r);
		auto mm = bit.query(dd);
		while(mm.FF.m <= cur.p){
			ans++;
			bit.erase(mm.SS);
			qq.push(mm.FF);
			mm = bit.query(dd);
		}
	}
	cout<<ans<<'\n';
	return 0;
}