先对所有元素以质量进行排序,
分块之后,在对同一块内元素以距离进行排序,
那么就有前一块元素的质量均小于当前块的质量,
根据这个性质,当前磁力块的磁力,会介于第$k$块元素,前$k-1$块磁力块的质量均小于磁力。
对于前$k-1$块磁力块,判断左端点元素的距离是否小于磁力块的吸引半径即可。
对于第$k$块暴力处理。
有个剪枝,若当前磁力块的吸引半径和磁力均小于之前的磁力块的最大吸引半径和磁力,那么这个磁力块无法更新任何一个状态。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
const int N=25e4+10;
const int B=505;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
int l[B],r[B],q[N],m[B];bool v[N];
struct node{ll dis,r;int m,p;}a[N];
inline bool cmp1(node a,node b){return a.m<b.m;}
inline bool cmp2(node a,node b){return a.dis<b.dis;}
int main()
{
int n;
ll x0,y0;qr(x0),qr(y0),qr(a[0].p),qr(a[0].r);a[0].r*=a[0].r;qr(n);
for(int i=1;i<=n;i++)
{
ll x,y;qr(x),qr(y),qr(a[i].m),qr(a[i].p),qr(a[i].r);
a[i].r*=a[i].r;a[i].dis=(x-x0)*(x-x0)+(y-y0)*(y-y0);
}
sort(a+1,a+n+1,cmp1);
int bl=sqrt(n),sz=bl;
for(int i=1;i<=sz;i++)
{
l[i]=r[i-1]+1;r[i]=i*bl;m[i]=a[r[i]].m;
sort(a+l[i],a+r[i]+1,cmp2);
}
if(r[sz]<n){l[sz+1]=r[sz]+1;r[++sz]=n;m[sz]=a[r[sz]].m;sort(a+l[sz],a+r[sz]+1,cmp2);}
int head=-1,tail=0;q[0]=0;ll mx=0,mp=0;
while(head<=tail)
{
node x=a[q[++head]];
if(x.r<=mx&&x.p<=mp)continue;
if(x.r>mx&&x.p>mp)mx=x.r,mp=x.p;
for(int i=1;i<=sz;i++)
{
if(m[i]>x.p)
{
for(int j=l[i];j<=r[i];j++)
if(!v[j]&&a[j].m<=x.p&&a[j].dis<=x.r)v[q[++tail]=j]=1;
break;
}
while(l[i]<=r[i]&&a[l[i]].dis<=x.r)
{
if(!v[l[i]])q[++tail]=l[i];
++l[i];
}
}
}
qw(head-1);puts("");
return 0;
}
最后一次更新于2019-10-11
0 条评论