RT,以下这份代码吸氧是 40pts,不吸氧就可以 \texttt\green{AC}。有有没有巨佬可以给出合理的解释,在线等。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int n,T,ans;
int L[N],R[N],pos[N],maxblk[N];
bool vis[N];
struct Stone{
int x,y,m,p,r;
int dis;
}a[N];
bool cmp1(Stone x,Stone y){
return x.m<y.m;
}
bool cmp2(Stone x,Stone y){
return x.dis<y.dis;
}
void Prework(){
T=sqrt(n);
for(int i=1;i<=T;i++)
L[i]=R[i-1]+1,R[i]=i*T;
if(R[T]<n){
T++;
L[T]=R[T-1]+1,R[T]=n;
}
for(int i=1;i<=T;i++){
sort(a+L[i],a+R[i]+1,cmp2);
for(int j=L[i];j<=R[i];j++){
pos[j]=i;
maxblk[i]=max(maxblk[i],a[j].m);
}
}
return;
}
void BFS(){
queue<Stone>q;
q.push(a[0]);
vis[0]=1;
while(!q.empty()){
Stone t=q.front();
q.pop();
int pos=1;
while(maxblk[pos]<=t.p)
pos++;
for(int i=1;i<=pos-1;i++){
while(L[i]<=R[i]&&a[L[i]].dis<=t.r){
if(!vis[L[i]]){
vis[L[i]]=1,ans++;
q.push(a[L[i]]);
}
L[i]++;
}
}
if(pos==T+1)
continue;
for(int i=L[pos];i<=R[pos];i++){
if(a[i].dis<=t.r&&a[i].m<=t.p&&!vis[i]){
ans++,vis[i]=1;
q.push(a[i]);
}
}
}
return;
}
signed main(){
cin>>a[0].x>>a[0].y>>a[0].p>>a[0].r>>n;
a[0].r*=a[0].r;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y>>a[i].m>>a[i].p>>a[i].r;
a[i].r*=a[i].r;
a[i].dis=(a[i].x-a[0].x)*(a[i].x-a[0].x)+(a[i].y-a[0].y)*(a[i].y-a[0].y);
}
sort(a+1,a+n+1,cmp1);
Prework();
BFS();
cout<<ans;
return 0;
}