QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#295774	#5463. Range Closest Pair of Points Query	ushg8877	WA	126ms	42292kb	C++14	2.2kb	2023-12-31 22:18:13	2023-12-31 22:18:14

Judging History

你现在查看的是最新测评结果

[2023-12-31 22:18:14]
评测

测评结果：WA
用时：126ms
内存：42292kb

查看

[2023-12-31 22:18:13]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=2.5e5+5;
const int sqN=505;
int n,sq,q;
ll x[MAXN],y[MAXN],bx[MAXN],by[MAXN],p[MAXN];
ll ans[MAXN];
vector<int> sp[MAXN];
vector<pair<int,int> > que[MAXN];
struct ds{
// O(1)-O(sqrt(n)) 单点改、区间 min 
int le[MAXN],ri[MAXN],bel[MAXN],tot;
ll minn[sqN],val[MAXN];
void build(){
	sq=sqrt(n);
	while(ri[tot]!=n){
		le[tot+1]=ri[tot]+1;ri[tot+1]=min(le[tot+1]+sq,n);
		++tot;
	}
	for(int i=1;i<=tot;i++){
		for(int j=le[i];j<=ri[i];j++) bel[j]=i,val[j]=1e18; 
		minn[i]=1e18;
	} 
} 
void modify(int x,ll v){
	minn[bel[x]]=min(minn[bel[x]],v);val[x]=min(val[x],v);
}
ll ask(int l,int r){
	ll ans=1e18;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) ans=min(ans,val[i]);
		return ans; 
	}
	for(int i=l;i<=ri[bel[l]];i++) ans=min(ans,val[i]);
	for(int i=bel[l]+1;i<bel[r];i++) ans=min(ans,minn[i]);
	for(int i=le[bel[r]];i<=r;i++) ans=min(ans,val[i]);
	return ans; 
}
}B; 
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	for(int k=0;k<=30;k++){
		map<pair<int,int>,pair<int,int> > mp;
		for(int i=1;i<=n;i++) bx[i]=x[i]>>k,by[i]=y[i]>>k,p[i]=i;
		sort(p+1,p+n+1,[&](int x,int y){return (bx[x]!=bx[y]?bx[x]<bx[y]:(by[x]!=by[y]?by[x]<by[y]:x<y));});
		for(int l=1,r;l<=n;l=r+1){
			r=l;
			while(r<n&&bx[p[r+1]]==bx[p[l]]&&by[p[r+1]]==by[p[l]]) r++;
			mp[MP(bx[l],by[l])]=MP(l,r);
		}
		auto add=[&](int l,int t,int x){for(int i=t;i>=t-5&&i>=l;i--) sp[x].push_back(p[i]);};
		for(auto i:mp){
			int x=i.first.first,y=i.first.second,l=i.second.first,r=i.second.second;
			for(int dx:{x-1,x,x+1}) for(int dy:{y-1,y,y+1}) if(mp.count(MP(dx,dy))){
				int L=mp[MP(dx,dy)].first,R=mp[MP(dx,dy)].second;
				int j=-1;
				for(int i=l;i<=r;i++){
					while(j+1<=R&&p[j+1]<p[i]) j++;
					add(L,j,p[i]);
				}
			}
		}
	}
	B.build();
	for(int i=1;i<=q;i++){
		int l,r;cin>>l>>r;
		que[r].push_back(MP(l,i));
	}
	for(int i=1;i<=n;i++){
		for(int j:sp[i]) if(j<i) B.modify(j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		for(auto q:que[i]) ans[q.second]=B.ask(q.first,i);
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 15384kb

input:

output:

result:

ok 5 number(s): "2 8 8 2 2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 15336kb

input:

output:

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 0ms

memory: 15340kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: -100

Wrong Answer

time: 126ms

memory: 42292kb

input:

20000 250000
3 10
5 4
4 7
1 5
2 1
10 6
2 3
8 4
2 1
8 5
9 8
7 7
4 5
2 7
9 4
9 10
3 2
9 5
10 2
9 2
3 1
9 9
6 5
9 5
9 10
9 1
1 2
8 8
3 4
7 6
6 2
6 8
6 6
8 4
10 2
1 1
10 2
8 3
4 4
5 5
5 1
4 9
7 6
6 8
6 4
1 6
10 3
3 2
4 10
6 8
9 7
2 10
7 8
10 7
3 2
5 1
6 4
7 9
1 3
4 9
4 8
9 4
5 2
2 2
9 2
9 2
9 6
6 9
8 7
...

output:

result:

wrong answer 5025th numbers differ - expected: '0', found: '1'