P10590

分块、bfs

#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;

#define div(...)
#define int long long

int x,y,n,sb,nb,ans;

struct Magnet{
	int x,y,m,p,r;
	__int128 dis;
};
Magnet a[250010];
queue<Magnet>q;
vector<Magnet>b[510];
int minmag[510];
bool vis[510][510];

bool cmpm(Magnet a,Magnet b){
	return a.m<b.m;
}
bool cmpdis(Magnet a,Magnet b){
	return a.dis>b.dis;
}

void bfs(){
	while(q.size()){
		Magnet f=q.front();
		q.pop();
		for(int i=1;i<=nb&&minmag[i]<=f.p;++i){
			while(b[i].size()){
				if(b[i].back().m>f.p){
					for(int j=b[i].size()-1;j>=0;--j){
						if(b[i][j].dis<=f.r&&b[i][j].m<=f.p&&vis[i][j]==0){
							ans++;
							q.push(b[i][j]);
							vis[i][j]=1;
						}
						else if(b[i][j].dis>f.r){
							break;
						}
					}
					break;
				}
				while(b[i].size()&&vis[i][b[i].size()-1]){
					b[i].pop_back();
				}
				if(b[i].size()&&b[i].back().dis<=f.r){
					ans++;
					q.push(b[i].back());
					b[i].pop_back();
				}
				else{
					break;
				}
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	div(input){
		Magnet l;
		cin>>x>>y>>l.p>>l.r>>n;
		l.r=l.r*l.r;
		q.push(l);
		for(int i=1;i<=n;++i){
			cin>>a[i].x>>a[i].y>>a[i].m>>a[i].p>>a[i].r;
			a[i].r=a[i].r*a[i].r;
			a[i].dis=(__int128)(a[i].x-x)*(a[i].x-x)+(__int128)(a[i].y-y)*(a[i].y-y);
		}
	}
	div(prework){
		sb=ceil(sqrt(n)),nb=ceil(1.0*n/sb);
		sort(a+1,a+n+1,cmpm);
		for(int i=1,nid=1,nsz=0;i<=n;++i){
			b[nid].push_back(a[i]);
			nsz++;
			if(nsz>=sb){
				nsz=0;
				nid++;
			}
		}
		for(int i=1;i<=nb;++i){
			minmag[i]=b[i].front().m;
			sort(b[i].begin(),b[i].end(),cmpdis);
		}
	}
	div(solve){
		bfs();
		cout<<ans;
	}
}