QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122508#5463. Range Closest Pair of Points QueryhxhhxhWA 242ms31216kbC++141.6kb2023-07-10 17:25:102023-07-10 17:25:13

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 17:25:13]
  • 评测
  • 测评结果:WA
  • 用时:242ms
  • 内存:31216kb
  • [2023-07-10 17:25:10]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,pos[400005],B=512,ans[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];
set<int>s;
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 rr){return (l.x*l.x+l.y*l.y)<(rr.x*rr.x+rr.y*rr.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[_],rt=0;
//		cout<<_<<"\t"<<i<<endl;
		auto o=s.insert(i).first;
		if(o!=s.begin()){
			for(auto t=prev(o);t!=s.begin()&&rt<=50;t--) T.cg(a[*t].id,dis(i,*t)),rt++;//,cout<<(*t)<<",";
			T.cg(a[*s.begin()].id,dis(i,*s.begin()));
		}
//		cout<<*s.begin()<<";";
		rt=0;
		for(auto t=next(o);t!=s.end()&&rt<=50;t++) T.cg(a[*t].id,dis(i,*t)),rt++;//,cout<<(*t)<<",";
//		cout<<endl;
		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: 1ms
memory: 24752kb

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: 3ms
memory: 21680kb

input:

2 1
1 1
1 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 4ms
memory: 21504kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: -100
Wrong Answer
time: 242ms
memory: 31216kb

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 423rd numbers differ - expected: '1', found: '1000000000000000000'