C++ 代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
const int N = 250010;
struct Stone
{
ll x, y, m, p, r;
ll bl;
double dis;
}st[N];
ll n, xx, yy, pl, rl;
int blo, ans;
int vis[N];
struct kuai
{
ll maxm, l;
}b[550];
queue<Stone> q;
inline ll re()
{
ll x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9'){if (c == '-') f= -1; c = getchar();}
while (c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
bool cmp(Stone a, Stone b)
{
return a.m < b.m;
}
bool cmp1(Stone a, Stone b)
{
if (a.bl == b.bl) return a.dis < b.dis;
else return a.bl < b.bl;
}
bool chk(int mid, int p)
{
return b[mid].maxm <= p;
}
int szfind(int p)
{
int l = 0, r = st[n].bl;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (chk(mid, p)) l = mid; else r = mid - 1;
}
return l;
}
int main()
{
xx = re(); yy = re(); pl = re(); rl = re(); n = re();
for (int i = 1; i <= n; ++i)
{
st[i].x = re(); st[i].y = re(); st[i].m = re(); st[i].p = re(); st[i].r = re();
st[i].dis = sqrt((st[i].x - xx) * (st[i].x - xx) + (st[i].y - yy) * (st[i].y - yy));
}
blo = sqrt(n);
sort(st + 1, st + n + 1, cmp);
for (int i = 1; i <= n; ++i) st[i].bl = (i - 1) / blo + 1;
for (int i = 1; i <= st[n].bl - 1; ++i)
{
b[i].l = (i - 1) * blo +1;
b[i].maxm = st[i*blo].m;
}
b[st[n].bl].l = (st[n].bl - 1) * blo + 1;
b[st[n].bl].maxm = st[n].m;
sort(st + 1, st + n + 1, cmp1);
Stone tem;
tem.x = xx; tem.y = yy; tem.p = pl; tem.r = rl;
q.push(tem);
while (!q.empty())
{
Stone u = q.front(); q.pop();
int k = szfind(u.p);
for (int t = 1; t <= k; ++t)
{
int j;
for (j = b[t].l; j <= min((ll)t * blo, n); ++j)
if (st[j].dis <= u.r)
{
if (!vis[j])
{
++ans; q.push(st[j]); vis[j] = 1;
}
}
else break;
b[t].l = j;
}
if (k != st[n].bl)
{
int j;
for (j = b[k+1].l; j <= min((ll)(k + 1) * blo, n); ++j)
if (st[j].dis <= u.r)
{
if (st[j].m <= u.p && !vis[j])
{
++ans; q.push(st[j]); vis[j] = 1;
}
}
else break;
}
}
printf("%d\n", ans);
return 0;
}