【悬关】求问
  • 板块P10590 磁力块
  • 楼主xuchuhan
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/5 17:19
  • 上次更新2024/7/5 19:43:53
查看原帖
【悬关】求问
785639
xuchuhan楼主2024/7/5 17:19

RT,以下这份代码吸氧是 40pts40pts,不吸氧就可以 \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;
}
2024/7/5 17:19
加载中...