CH#46A 磁力块

题意

磁力块 CH Round #46 - 「Adera 8」杯NOI模拟赛

描述

在一片广袤无垠的原野上，散落着N块磁石。每个磁石的性质可以用一个五元组(x,y,m,p,r)描述，其中x,y表示其坐标，m是磁石的质量，p是磁力，r是吸引半径。若磁石A与磁石B的距离不大于磁石A的吸引半径，并且磁石B的质量不大于磁石A的磁力，那么A可以吸引B。

小取酒带着一块自己的磁石L来到了这篇原野的(x0,y0)处，我们可以视为磁石L的坐标为(x0,y0)。小取酒手持磁石L并保持原地不动，所有可以被L吸引的磁石将会被吸引过来。在每个时刻，他可以选择更换任意一块自己已经获得的磁石（当然也可以是自己最初携带的L磁石）在(x0,y0)处吸引更多的磁石。小取酒想知道，他最多能获得多少块磁石呢？

输入格式

第一行五个整数x0,y0,pL,rL,N，表示小取酒所在的位置，磁石L磁力、吸引半径和原野上散落磁石的个数。

接下来N行每行五个整数x,y,m,p,r，描述一块磁石的性质。

输出格式

输出一个整数，表示最多可以获得的散落磁石个数（不包含最初携带的磁石L）。

样例输入

0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9

样例输出

3

数据范围与约定

• 对于30%的数据，1<=N<=1000。
• 对于100%的数据，1<=N<=250000，-10^9<=x,y<=10^9，1<=m,p,r<=10^9。

</article>


分析

容易想到BFS框架，需要判断哪些磁石能被吸引。能被吸引的条件是 质量≤磁力 且 距离≤吸引半径。考虑分块。

磁石按照质量排序后分成sqrt(N)块，每块内部按照距离排序。然后用每块获得的磁石去尝试吸引其它磁石。那么一定存在一个k，使得[1,k-1]块中的磁石质量都不大于该磁石的吸引力。相当于在前k-1块的开头取出若干磁石（均摊O(1)），在第k块中暴力扫描哪些磁石可以被取出（O(sqrt(N))），总复杂度\(O(N \sqrt{N})\)。这是最好写的做法。

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;co int N=2.5e5+1;
struct P{
int x,y,m,p,r;
}p[N],q[N];
bool b[N];
int n,L[N],R[N],M[N];
bool cmp(co P&a,co P&b){
return a.m<b.m;
}
bool cmp0(co P&a,co P&b){
return (ll)(a.x-q[0].x)*(a.x-q[0].x)+(ll)(a.y-q[0].y)*(a.y-q[0].y)<(ll)(b.x-q[0].x)*(b.x-q[0].x)+(ll)(b.y-q[0].y)*(b.y-q[0].y);
}
bool pd(co P&a,co P&b){
return (ll)(q[0].x-b.x)*(q[0].x-b.x)+(ll)(q[0].y-b.y)*(q[0].y-b.y)<=(ll)a.r*a.r;
}
int main(){
//freopen(".in","r",stdin),freopen(".out","w",stdout);
read(q[0].x),read(q[0].y),read(q[0].p),read(q[0].r),read(n);
for(int i=1;i<=n;++i) read(p[i].x),read(p[i].y),read(p[i].m),read(p[i].p),read(p[i].r);
sort(p+1,p+n+1,cmp);
int t=sqrt(n);
for(int i=1;i<=t;++i){
L[i]=(i-1)*t+1,R[i]=i*t,M[i]=p[R[i]].m;
sort(p+L[i],p+R[i]+1,cmp0);
}
if(R[t]<n){
L[t+1]=R[t]+1,R[++t]=n,M[t]=p[R[t]].m;
sort(p+L[t],p+R[t]+1,cmp0);
}
int l=0,r=1; // [l,r)
while(l<r){
int k=0;
for(int i=1;i<=t;++i){
if(M[i]<=q[l].p) k=i;
else break;
}
for(int i=1;i<=k;++i)
while(L[i]<=R[i]&&pd(q[l],p[L[i]])){
if(!b[L[i]]) b[L[i]]=1,q[r++]=p[L[i]];
++L[i];
}
if(k++!=t)for(int i=L[k];i<=R[k];++i)
if(!b[i]&&p[i].m<=q[l].p&&pd(q[l],p[i]))
b[i]=1,q[r++]=p[i];
++l;
}
printf("%d\n",r-1);
return 0;
}