C++14(g++5.4) 解法, 执行用时: 260ms, 内存消耗: 21984K, 提交时间: 2020-04-27 20:50:00

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 250005;
struct node {
	ll d, m, p, r;
} mag[N];
ll  maxdis[510];
int lef[510], rig[510], vis[N];

bool cmp_d(node a, node b) {
	return a.d < b.d;
}
bool cmp_m(node a, node b) {
	return a.m < b.m;
}

int main(void) {
	int n;
	ll sx, sy;
	scanf("%lld%lld%lld%lld%d", &sx, &sy, &mag[0].p, &mag[0].r, &n);
	mag[0].r *= mag[0].r;

	ll x, y;
	for (int i = 1; i <= n; i++) {
		scanf("%lld%lld%lld%lld%lld", &x, &y, &mag[i].m, &mag[i].p, &mag[i].r);
		mag[i].d = (x - sx) * (x - sx) + (y - sy) * (y - sy);
		mag[i].r *= mag[i].r;
	}

	sort(mag + 1, mag + 1 + n, cmp_d);

	int cnt = 0, len = sqrt(n);
	for (int i = 1; i <= n; i += len) {
		lef[++cnt] = i;
		rig[cnt] = min(n, i + len - 1);
		maxdis[cnt] = mag[rig[cnt]].d;
		sort(mag + lef[cnt], mag + 1 + rig[cnt], cmp_m);
	}

	int ans = -1;
	queue<int>q;
	q.push(0);
	vis[0] = 1;
	while (!q.empty()) {
		int s = q.front();
		q.pop();
		++ans;
		ll u = mag[s].r;//引力半径
		ll p = mag[s].p;//引力

		for (int i = 1; i <= cnt; i++) {
			if (maxdis[i] <= u) {
				for (int& j = lef[i]; j <= rig[i] && mag[j].m <= p; j++) {
					if (!vis[j]) {
						q.push(j);
						vis[j] = 1;
					}
				}
			} else {
				for (int j = lef[i]; j <= rig[i]; j++) {
					if (!vis[j] && mag[j].m <= p && mag[j].d <= u) {
						vis[j] = 1;
						q.push(j);
					}
				}
				break;
			}
		}
	}
	printf("%d\n", ans);

	return 0;
}

C++ 解法, 执行用时: 489ms, 内存消耗: 10232K, 提交时间: 2021-09-18 18:03:58

#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
typedef long long ll;
const int N=2e6+10;
const int w=500;
struct node{
	ll d,r;
	ll m,p;
}a[N]; 
ll d[N],x0,y_0,l[N],r[N],v[N],n,cnt;
queue<ll>q; 
bool cmp_d(node a,node b){
	return a.d<b.d;
}
bool cmp_m(node a,node b){
	return a.m<b.m;
}
int main(){
cin>>x0>>y_0>>a[0].p>>a[0].r>>n;
a[0].r*=a[0].r;
for(int i=1;i<=n;i++)
{
	ll x,y;
	cin>>x>>y>>a[i].m>>a[i].p>>a[i].r;
	a[i].r*=a[i].r; 
	a[i].d=(x0-x)*(x0-x)+(y_0-y)*(y_0-y); 
}
sort(a+1,a+1+n,cmp_m);
for(ll i=1;i<=n;i+=w)
{
	l[++cnt]=i;
	r[cnt]=min(n,i+w-1);
	d[cnt]=a[r[cnt]].m;
	sort(a+l[cnt],a+r[cnt]+1,cmp_d);
}
q.push(0);
ll ans=1;
while(q.size())
{
	ll t=q.front(),ri=a[t].r,p=a[t].p;
	q.pop();
	for(ll i=1;i<=cnt;i++)
	{
		if(d[i]>p)
		{
			for(ll j=l[i];j<=r[i];j++)
			 if(!v[j]&&a[j].d<=ri&&a[j].m<=p)
			 {
			 	q.push(j);
			 	ans++;
			 	v[j]=1;
			 }
			 break;
		}
		while(l[i]<=r[i]&&a[l[i]].d<=ri)
		{
			if(!v[l[i]])
			{
				q.push(l[i]);
				ans++;
			}
			++l[i];
		}
	}
}
cout<<ans-1;
	return 0;
}