WA了一个点求调
  • 板块P10590 磁力块
  • 楼主Gmj2020
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/21 09:46
  • 上次更新2024/9/21 12:12:21
查看原帖
WA了一个点求调
1372776
Gmj2020楼主2024/9/21 09:46
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+4e6;
struct node{
	int p,r,m,id;
	long long R;
}a[N];
int x,y,p,r,n,len;
bool cmp(node a,node b){
	return a.R<b.R;
}
bool cmp1(node a,node b){
	if(a.id==b.id)return a.m<b.m;
	return a.id<b.id;
}
long long mr[600];
int L=-1,h[600],e[600];
queue<node>q;
bool v[N];
int cnt=-1;
int main(){
	cin>>x>>y>>p>>r>>n;
	for(int i=1;i<=n;i++){
		long long X,Y;
		cin>>X>>Y>>a[i].m>>a[i].p>>a[i].r;
		long long R=(X-x)*(X-x)+(Y-y)*(Y-y);
		a[i].R=R; 
	}
	sort(a+1,a+1+n,cmp);
	int len=sqrt(n);
	for(int i=1;i<=n;i++){
		a[i].id=(i-1)/len;
		if(a[i].id==L+1)e[L]=i-1,L++,h[L]=i;
		mr[a[i].id]=max(mr[a[i].id],a[i].R);
	}
	e[L]=n;
	sort(a+1,a+1+n,cmp1);
	q.push({p,r,0,0,0});
	//for(int i=0;i<=L;i++)cout<<h[i]<<" "<<e[i]<<'\n';
	while(q.size()){
		auto t=q.front();
		q.pop();
		cnt++;
		int j=0;
		while(j<=L&&mr[j]<=1ll*t.r*t.r){
			while(h[j]<=e[j]&&a[h[j]].m<=t.p){	
				if(!v[h[j]])
				 q.push({a[h[j]].p,a[h[j]].r,0,0,0});
				h[j]++;
			}
			j++;
		}
		if(j<=L){
			for(int i=h[j];i<=e[j];i++){
				if(a[i].m>t.p)break;
				if(v[i])continue;
				if(a[i].R<=1ll*t.r*t.r){
					q.push({a[h[j]].p,a[h[j]].r,0,0,0});
					v[i]=true;
				}
			}
		}
	}
	cout<<cnt;
	return 0;	
}
2024/9/21 09:46
加载中...