QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122463#5463. Range Closest Pair of Points QueryfansizheWA 2572ms39832kbC++231.8kb2023-07-10 15:40:112023-07-10 15:40:12

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:40:12]
  • 评测
  • 测评结果:WA
  • 用时:2572ms
  • 内存:39832kb
  • [2023-07-10 15:40:11]
  • 提交

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
#define ld long double
int n,q,B;
const int S=500;
ld ex[250005],ey[250005];
struct node{
	ld x,y;
	int id;
	bool operator <(const node &b)const{return x<b.x;}
}a[250005];
int b[250005];
int pos[250005],L[505],R[505];
vector<pair<int,int> > Query[250005];
ll ans[250005];
ll val[250005],mn[505];
ll getdis(ld x,ld y){return (ll)round(x*x+y*y);}
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");
	srand(114514);
	n=read(),q=read();B=sqrt(n);
	ld cs=1.0*rand()/RAND_MAX,sn=sqrt(1-cs*cs);
	for(int i=1;i<=n;i++){
		ld x=read(),y=read();
		ex[i]=a[i].x=x*cs-y*sn,ey[i]=a[i].y=x*sn+y*cs;
		a[i].id=i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		b[a[i].id]=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);ld x=ex[i],y=ey[i];
		for(int j=max(1,b[i]-S);j<=lim;j++)if(a[j].id<i)add(a[j].id,getdis(a[j].x-x,a[j].y-y));
		for(int j=max(1,i-S);j<i;j++)add(j,getdis(ex[j]-x,ey[j]-y));
		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: 4ms
memory: 17960kb

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

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

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0
Accepted
time: 216ms
memory: 23680kb

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:

ok 250000 numbers

Test #5:

score: 0
Accepted
time: 215ms
memory: 23672kb

input:

20000 250000
72 45
72 34
34 10
20 96
79 39
43 5
72 49
56 85
1 72
44 70
73 89
69 76
49 89
57 38
39 9
33 47
22 3
96 41
90 82
25 6
72 92
73 38
53 21
16 88
59 9
54 2
14 6
7 94
99 68
27 82
70 50
81 81
60 81
2 98
33 19
98 9
35 36
49 66
86 7
3 95
32 89
62 42
68 88
65 16
94 6
85 10
51 69
90 36
70 87
13 79
4...

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
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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...

result:

ok 250000 numbers

Test #6:

score: 0
Accepted
time: 220ms
memory: 23720kb

input:

20000 250000
116 165
150 677
951 676
552 324
267 222
739 755
705 663
235 142
152 714
735 641
414 201
313 663
683 300
403 739
37 521
42 833
553 733
886 449
86 913
55 637
731 932
143 161
500 891
719 79
916 237
431 992
804 210
643 332
165 362
178 332
821 510
762 34
188 83
283 357
743 407
750 487
19 658...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
1
0
1
0
0
0
2
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
4
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
52
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
5
0
0
0
0
0
1
0
0
0
1
1
0
0
0
2
0
0
0
0
0
0
...

result:

ok 250000 numbers

Test #7:

score: 0
Accepted
time: 224ms
memory: 23920kb

input:

20000 250000
193144 901630
894860 3728
802840 155641
625273 792794
433205 942335
223506 874548
425235 550629
341169 950916
49296 305542
709463 512381
9742 994078
106664 845553
38691 373010
184728 331946
344567 438182
854583 291040
94405 555036
56330 494420
928479 123077
796593 798314
300374 490072
2...

output:

3576676
1219565
93925
2336788
8872
68
137
842657
137
8560936
13914025
28521
88362
8872
8872
52996
12869
86297
68
8137625
93925
12869
86297
8872
8872
8872
47888
8872
12869
107860
12869
59536
59536
425540
12869
59536
8872
93925
117225
137
137
52996
68
52996
137
8872
68
12869
137
68
86297
1514
159700
6...

result:

ok 250000 numbers

Test #8:

score: 0
Accepted
time: 219ms
memory: 23676kb

input:

20000 250000
65468917 46637638
46041830 58072288
95596278 49154795
57837493 40861050
21328886 69542502
7729300 7126264
2317013 48080367
75669670 20165373
93996778 88884044
8523082 62327896
123901 11925128
71901024 73104267
94991893 98591670
53591520 11543761
76785613 86286274
64694742 89591932
75687...

output:

185588005
3282196826
141969393
25769005
141969393
185588005
576346153849
141969393
141969393
185588005
141969393
141969393
141969393
141969393
135584833
141969393
141969393
485404589
1182793
1182793
35224007589
135584833
185588005
931246420
185588005
25769005
375240717
141969393
2245310308
239709665...

result:

ok 250000 numbers

Test #9:

score: 0
Accepted
time: 2343ms
memory: 39772kb

input:

250000 250000
1 2
1 1
3 2
3 3
1 2
3 2
1 2
1 3
3 1
2 1
1 3
2 3
3 3
1 3
3 1
3 1
1 3
2 1
1 2
1 1
1 2
2 2
1 2
1 2
1 3
3 3
1 1
3 2
1 2
2 2
1 1
2 3
3 2
2 1
3 3
2 1
2 3
3 1
2 3
3 2
2 1
1 1
3 2
1 2
1 3
3 1
2 3
2 1
1 2
1 1
1 2
3 3
1 2
2 2
3 1
3 1
3 1
1 2
2 2
1 1
3 3
1 3
1 3
1 2
1 2
3 1
3 2
1 2
2 2
1 2
1 1
2 ...

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:

ok 250000 numbers

Test #10:

score: -100
Wrong Answer
time: 2572ms
memory: 39832kb

input:

250000 250000
65 333
64 141
52 164
104 499
329 292
187 279
178 394
92 488
223 487
457 262
355 475
466 223
450 293
397 22
390 379
257 389
339 162
228 267
446 78
116 3
28 400
63 319
255 491
459 301
340 321
183 340
469 6
288 268
383 446
456 13
478 383
109 79
142 317
132 219
168 347
30 398
59 453
192 33...

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
1
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
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 97665th numbers differ - expected: '1', found: '2'