QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122495#5463. Range Closest Pair of Points QueryhxhhxhWA 201ms34360kbC++141.3kb2023-07-10 16:50:022023-07-10 16:50: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 16:50:03]
  • 评测
  • 测评结果:WA
  • 用时:201ms
  • 内存:34360kb
  • [2023-07-10 16:50:02]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,pos[400005],B=512,ans[400005];
bool t[400005];
struct SEG{
	int r[400005],t[555];
	void init(){
		memset(r,0x3f,sizeof(r));
		memset(t,0x3f,sizeof(t));
	}
	void cg(int x,int v){
		t[x>>9]=min(t[x>>9],v);
		r[x]=min(r[x],v);
	}
	int que(int L,int R){
		int res=1e18;
		for(int i=L;i<=L+B&&i<=R;i++) res=min(res,r[i]);
		for(int i=R;i>=R-B&&i>=L;i--) res=min(res,r[i]);
		for(int i=(L>>9)+1;i<(R>>9);i++) res=min(res,t[i]);
		return res;
	}
}T;
struct st{
	int x,y,id;
}a[400005];
struct qt{
	int l,r;
}c[400005];
vector<int>r[400005];
int dis(int x,int y){
	return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) scanf("%lld %lld",&a[i].x,&a[i].y),a[i].id=i;
	sort(a+1,a+n+1,[&](st l,st r){return (l.x*l.x+l.y*l.y)<(r.x*r.x+r.y*r.y);});
	for(int i=1;i<=n;i++) pos[a[i].id]=i;
	for(int i=1;i<=q;i++){
		scanf("%lld %lld",&c[i].l,&c[i].r);
		r[c[i].r].push_back(i);
	}
	T.init();
	for(int _=1;_<=n;_++){
		int i=pos[_];
		for(int j=max(1ll,i-B);j<=B&&j<=n;j++) if(t[j]) T.cg(a[j].id,dis(i,j));
		t[i]=1;
		for(int j:r[_]) ans[j]=T.que(c[j].l,c[j].r);
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 21724kb

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: 1ms
memory: 24584kb

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: 22404kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: -100
Wrong Answer
time: 201ms
memory: 34360kb

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
1000000000000000000
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
1
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 70th numbers differ - expected: '0', found: '1000000000000000000'