QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122469#5463. Range Closest Pair of Points QueryfansizheWA 125ms23716kbC++231.7kb2023-07-10 15:53:012023-07-10 15:53:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-10 15:53:03]
  • 评测
  • 测评结果:WA
  • 用时:125ms
  • 内存:23716kb
  • [2023-07-10 15:53:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+(c^'0'),c=getchar();
	return x;
}
#define ll long long
int n,q,B;
const int S=500;
ll x[250005],y[250005];
double ex[250005];
int a[250005],b[250005];
bool cmp(int x,int y){return ex[x]<ex[y];}
int pos[250005],L[505],R[505];
vector<pair<int,int> > Query[250005];
ll ans[250005];
ll val[250005],mn[505];
ll getdis(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}
void init(){
	for(int i=1;i<=n;i++)val[i]=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=pos[n];i++)mn[i]=0x3f3f3f3f3f3f3f3f;
}
void add(int x,ll y){
	val[x]=min(val[x],y);
	mn[pos[x]]=min(mn[pos[x]],y);
}
ll ask(int l){
	ll res=0x3f3f3f3f3f3f3f3f;
	for(int i=pos[l]+1;i<=pos[n];i++)res=min(res,mn[i]);
	for(int i=l;i<=R[pos[l]];i++)res=min(res,val[i]);
	return res;
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
//	puts("OK");
	n=read(),q=read();B=sqrt(n);
	double cs=cos(114514),sn=sin(114514);
	for(int i=1;i<=n;i++)x[i]=read(),y[i]=read(),ex[i]=x[i]*cs-y[i]*sn;
	for(int i=1;i<=n;i++)a[i]=i;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)b[a[i]]=i;
	for(int i=1;i<=n;i++){
		pos[i]=(i-1)/B+1;
		if(!L[pos[i]])L[pos[i]]=i;
		R[pos[i]]=i;
	}
	for(int i=1;i<=q;i++){
		int l=read(),r=read(); 
		Query[r].push_back(make_pair(l,i));
	}
	init();
	for(int i=1;i<=n;i++){
		int lim=min(n,b[i]+S);
		for(int j=max(1,b[i]-S);j<=lim;j++)if(a[j]<i)add(a[j],getdis(b[j],i));
		for(int j=max(1,i-S);j<i;j++)add(j,getdis(j,i));
		for(auto p:Query[i])ans[p.second]=ask(p.first);
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 19892kb

input:

5 5
2 4
1 1
3 3
5 1
4 2
1 5
2 3
2 4
3 5
1 3

output:

2
8
8
2
2

result:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 22140kb

input:

2 1
1 1
1 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 19972kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: -100
Wrong Answer
time: 125ms
memory: 23716kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 2145th numbers differ - expected: '4', found: '2'