易错点:
- 和 要用long long存储.
- 读入的吸引半径需要乘方(因为通过(x-x0)(x-x0)-(y-y0)(y-y0)获取的值本身就是乘方的).
(分块)右端点需要用min(n,i+w-1)获取.
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int MAXN=3e5;
struct Node{
ll dis,r;
int m,p;
}a[MAXN];
bool cmp_dis(Node a,Node b){
return a.dis<b.dis;
}
bool cmp_m(Node a,Node b){
return a.m<b.m;
}
int q[MAXN],l,r;
int L[MAXN],R[MAXN],cnt=0;
ll D[MAXN];
bool vis[MAXN];
int main(){
ll x0,y0;
int n;
scanf("%lld%lld%d%lld%d",&x0,&y0,&a[0].p,&a[0].r,&n);
a[0].r*=a[0].r;
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d%d%d%lld",&x,&y,&a[i].m,&a[i].p,&a[i].r);
a[i].dis=(x-x0)*(x-x0)+(y-y0)*(y-y0);
a[i].r*=a[i].r;
}
sort(a+1,a+n+1,cmp_dis);//先按距离排序
int w=sqrt(n);
for(int i=1;i<=n;i+=w){
L[++cnt]=i,R[cnt]=min(n,i+w-1);
D[cnt]=a[R[cnt]].dis;
sort(a+L[cnt],a+R[cnt]+1,cmp_m);//+1
}
l=r=1,q[1]=0;
while(l<=r){
ll rad=a[q[l]].r;
int p=a[q[l]].p;
l++;
for(int i=1;i<=cnt;i++){
if(D[i]>rad){
for(int j=L[i];j<=R[i];j++){
if(!vis[j]&&a[j].dis<=rad&&a[j].m<=p){
vis[j]=1;
q[++r]=j;
}
}
break;
}
while(L[i]<=R[i]&&a[L[i]].m<=p){
if(!vis[L[i]])
q[++r]=L[i];
L[i]++;
}
}
}
printf("%d\n",r-1);
return 0;
}
梁宇晨0,我是你的dad
Liang Yuchen,I am your father
就是@qqqqqqqq
我是你爹
我是张柯锐
冒充我干嘛
funny mud go pea
我是张柯锐
冒充我干嘛
我是张柯锐
冒充我干嘛
我是张柯锐
冒充我干嘛
我是张柯锐
冒充我干嘛
我是张柯锐
冒充我干嘛
冒充我干嘛
冒充我干嘛
冒充我干嘛
冒充我干嘛
冒充我干嘛
我是张柯锐
我是张柯锐
我是张柯锐
我是张柯锐
我是张柯锐
我是张柯锐
我是张柯锐
我是张柯锐
我是张柯锐