QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#718891#9613. 计算几何Akagi_shigeru76 826ms252564kbC++231.8kb2024-11-06 21:42:332024-11-06 21:42:33

Judging History

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

  • [2024-11-06 21:42:33]
  • 评测
  • 测评结果:76
  • 用时:826ms
  • 内存:252564kb
  • [2024-11-06 21:42:33]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
ll read(){
	char c=getchar();
	ll x=0,f=1;
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+(c^48);
		c=getchar();
	}
	return x*f;
}
void write(ll x){
	static char buf[40];
	static int len=0;
	do{
		buf[++len]=x%10+48;
		x/=10;
	}while(x);
	while(len) putchar(buf[len--]);
}
const ll inf=1e18;
const ll maxn=1e6+10;
ll n,q,ans[maxn];
struct que{
	ll l,r,id;
};
struct point{
	ll x,y,id;
	bool operator < (const point tmp) const{
		return x<tmp.x;
	}
}p[maxn],tmp[maxn];
ll dis(point a,point b){
	return abs(a.x-b.x)+abs(a.y-b.y);
}
pair<ll,ll> cal(ll l,ll r){
	ll res1=0,res2=0,ans=inf,cnt=0;
	for(ll i=l;i<=r;i++) tmp[++cnt]=p[i];
	sort(tmp+1,tmp+cnt+1);
	for(ll i=1;i<=cnt;i++){
		for(ll j=i+1;j<=i+20&&j<=cnt;j++){
			if(dis(tmp[i],tmp[j])<ans){
				ans=dis(tmp[i],tmp[j]);
				res1=tmp[i].id,res2=tmp[j].id;
			}
		}
	}
	if(res1>res2) swap(res1,res2);
	return {res1,res2};
}
void solve(ll l,ll r,vector<que> v){
	if(v.empty()) return;
	// cout<<l<<" "<<r<<":\n";
	pair<ll,ll> res=cal(l,r);
	vector<que> v1,v2;
	for(auto it:v){
		if(it.l<=res.first&&it.r>=res.second) ans[it.id]=dis(p[res.first],p[res.second]);
		else if(it.l>res.first) v2.push_back(it);
		else v1.push_back(it);
	}
	// cout<<res.first<<" "<<res.second<<"\n";
	solve(l,res.second-1,v1),solve(res.first+1,r,v2);
}
int main(){
	// freopen("geo3.in","r",stdin);
	n=read(),q=read();
	for(ll i=1;i<=n;i++) p[i].x=read(),p[i].y=read(),p[i].id=i;
	vector<que> v;
	for(ll i=1;i<=q;i++){
		ll l=read(),r=read();
		v.push_back({l,r,i});
	}
	solve(1,n,v);
	for(ll i=1;i<=q;i++) write(ans[i]),putchar('\n');
}

详细


Pretests


Final Tests

Test #1:

score: 4
Accepted
time: 4ms
memory: 10016kb

input:

2000 2000
983850330 731103020
513263912 234227610
788795134 228585831
-983909940 -814082030
-582261039 729875680
617950974 -259602422
-355311469 355769341
-394119311 -493842356
899026446 -402238603
-300533665 433674923
946553927 26786776
46270288 43713228
-838909861 427788951
863776211 691106038
-93...

output:

511457
511457
1660620
25525096
1660620
511457
9525149
57819607
1660620
1660620
511457
1660620
511457
511457
1660620
7013046
511457
1660620
7013046
1660620
1660620
511457
3297708
1660620
1660620
3297708
1660620
1660620
1660620
3297708
4830700
8953781
511457
511457
1660620
1660620
1660620
8953781
5114...

result:

ok 2000 numbers

Test #2:

score: 4
Accepted
time: 3ms
memory: 10056kb

input:

2000 2000
407439483 0
-924180082 0
534637753 0
-836707453 0
-385278990 0
90204634 0
454360393 0
-895242427 0
-112231538 0
-323497705 0
368203671 0
-124641980 0
183953551 0
596609116 0
666423112 0
706701157 0
988299741 0
-248457324 0
-507127215 0
610030981 0
356918300 0
110156240 0
317203493 0
754544...

output:

1043672
417
1362
417
1362
1362
417
6857
417
2658
90109
1021
417
2658
269047
2241
2241
417
417
2658
2658
417
417
14980
1362
1362
90109
1362
56414
1021
207612
2658
1021
417
417
1362
1362
417
417
1021
1362
40782
417
1362
1021
417
417
417
2241
6857
1021
1021
417
2658
1021
417
1362
417
417
417
417
1362
4...

result:

ok 2000 numbers

Test #3:

score: 4
Accepted
time: 48ms
memory: 10864kb

input:

20000 20000
-721847248 671834627
-750033826 -893098471
358123311 740735694
-15749050 352553172
331628828 285387115
-870680297 30680547
747479743 495644671
-24785538 458380663
-49052185 540025540
192115219 694762799
-582891748 -643029079
-356894103 726491498
213744952 457769371
-357728988 745592631
-...

output:

384993
109364
882199
184464
184464
109364
109364
109364
109364
109364
109364
264720
384993
109364
109364
184464
184464
109364
109364
109364
109364
184464
184464
109364
264720
364852
264720
109364
109364
364852
109364
364852
184464
184464
109364
264720
1619872
364852
109364
184464
478876
109364
10936...

result:

ok 20000 numbers

Test #4:

score: 4
Accepted
time: 58ms
memory: 12856kb

input:

20000 20000
-856287 613193
884980 313749
-51917 -595036
-515889 732611
768011 201825
685038 -690361
-825296 610210
693313 378198
153998 -220528
-881367 -427847
-762386 726194
-882783 -396975
-585188 -646369
852468 -769564
845740 446417
-272832 806448
-23829 -843528
-290649 -509815
183302 929309
-810...

output:

398
441
17
254
17
1529
17
263
254
263
263
263
17
17
309
263
398
263
263
509
17
441
263
17
17
263
509
17
17
441
17
17
477
263
377
263
309
17
254
17
263
263
398
17
263
1022
477
17
17
377
477
415
17
1059
377
256
256
263
17
254
17
709
17
7667
263
17
271
17
17
263
271
398
398
377
17
17
17
441
17
17
263
2...

result:

ok 20000 numbers

Test #5:

score: 4
Accepted
time: 60ms
memory: 12688kb

input:

20000 20000
272933 -400117
36074 -350576
-180416 245927
-152816 -532917
-815869 -121672
900928 561561
696604 -34106
281988 -30073
37999 -748187
-260504 367199
-254538 984542
-929979 -597816
735632 -731486
-88688 -820300
-180173 516379
319782 -306180
461815 88179
-863913 497662
-972928 920984
670858 ...

output:

663
321
166
497
259
183
259
259
166
166
183
166
259
166
949
166
259
559
166
321
166
1215
166
183
1131
1215
259
183
919
166
1131
166
905
166
624
166
718
3226
166
166
624
321
259
166
166
259
663
259
183
2887
718
554
166
183
259
166
166
183
554
183
166
321
1860
166
166
259
259
166
259
166
259
3588
166
...

result:

ok 20000 numbers

Test #6:

score: 4
Accepted
time: 54ms
memory: 14336kb

input:

20000 20000
961714 0
-256591 0
858025 0
302536 0
989232 0
921482 0
132252 0
-687494 0
976712 0
584368 0
-379471 0
-368374 0
-421478 0
-269707 0
-840836 0
683604 0
-233785 0
-509259 0
691924 0
-326966 0
699666 0
-602646 0
-394566 0
-762188 0
-721221 0
110375 0
123249 0
-679471 0
476495 0
-247891 0
-6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
1
0
0
0
36
0
847
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
10
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
4
605
11
0
0
1
0
0
0
0
0
0
0
0
65
0
0
0
0
0
2
0
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 20000 numbers

Test #7:

score: 4
Accepted
time: 50ms
memory: 12000kb

input:

20000 20000
931651 0
-193344 0
-459921 0
-208681 0
265915 0
221047 0
-976889 0
836902 0
-128302 0
775194 0
523077 0
-398264 0
296667 0
-324286 0
477274 0
226741 0
-70369 0
627346 0
-81394 0
525865 0
454142 0
708462 0
-629738 0
-171617 0
-745312 0
-647420 0
-249238 0
-911374 0
255729 0
565402 0
-3974...

output:

1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
5
227
0
0
0
0
0
0
1
3
0
0
0
0
0
0
1
41
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
18
0
0
0
0
0
0
0
0
18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
52
0
0
0
0
0
0
0
0
0
0
0
306
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 20000 numbers

Test #8:

score: 4
Accepted
time: 49ms
memory: 12072kb

input:

20000 20000
286328653 0
-436132873 0
-950502327 0
62507734 0
410183824 0
-244422860 0
-89619254 0
-36224025 0
987264815 0
-366170043 0
789288990 0
595133547 0
129243363 0
480765515 0
-367270251 0
85317458 0
-717834130 0
990039646 0
601945059 0
979377776 0
487802144 0
-543661591 0
-649863532 0
530289...

output:

1
1
469
1564
1668
1
4
1
1659
1
4
1
1
4
1
14
1
428
4
1
1
32
1
13372
4
1
688
4
7
4
4
7
1
7
1
1
1
1
1
37
644
437
91
7
18
104
1
1
1
1
18
1
37
14
37
1
1
306
18
1
7
1601
45
14
14
1
1
1244
32
553
1
37
1225
1
37
1
1
7
1
1
1
4
7
37
14
7
1
1
1
23657
1
104
17499
18
1
1
1
1
37
1
1
14
1
4
7
37
484
1
1
1
836
1
1
...

result:

ok 20000 numbers

Test #9:

score: 4
Accepted
time: 826ms
memory: 50632kb

input:

200000 200000
-412960500 577830338
99802584 -136950865
-950307156 -859369040
793568959 -565815756
411737945 -479377622
569675957 -601905445
-417176412 -729638186
200119881 -430545998
-86043427 969867029
64175162 -427861527
83451953 -756750354
-748032722 43908052
418515829 494502750
346664686 9215021...

output:

9239
9239
9239
9239
9239
75958
648460
9239
81454
9239
9239
9239
35946
9239
9239
30950
19566
9239
9239
9239
9239
27060
30950
9239
19566
19634
35946
27060
35946
9239
35946
27060
9239
9239
59843
9239
9239
9239
9239
9239
19634
9239
9239
35946
9239
9239
9239
84971
344383
9239
9239
19634
19634
59843
9239
...

result:

ok 200000 numbers

Test #10:

score: 4
Accepted
time: 685ms
memory: 43924kb

input:

200000 200000
215020 -29462
152216 -199822
-604632 -191567
10263 -830451
-89159 -121408
-881329 -921244
-809798 -903639
29060 -438373
-393896 -438778
79484 803288
646060 323407
-150152 23631
-509647 -88435
-772163 923612
-832132 -270978
650123 -731403
997559 -457855
797171 863407
366847 -915734
-700...

output:

3
3
3
60
3
3
28
3
15
3
31
60
3
3
3
3
3
3
3
3
31
15
3
28
3
3
28
17
31
3
283
120
3
3
239
3
3
15
120
3
15
134
15
15
120
3
3
3
15
15
3
3
15
3
3
3
109
3
27
3
3
15
3
3
3
3
3
90
2780
28
3
3
3
3
3
3
15
3
752
3
3
15
3
66
31
3
3
3
3
16
3
3
3
60
15
109
45
3
105
3
3
15
3
105
3
3
3
3
3
27
30
15
3
3
15
3
3
15
15
...

result:

ok 200000 numbers

Test #11:

score: 4
Accepted
time: 704ms
memory: 49544kb

input:

200000 200000
-814016 -440530
-988229 -214220
-825745 -268031
808279 -507843
-365671 559807
-823503 84191
685041 -755331
-379355 -288337
-730097 156308
-49982 -920817
135131 710420
786978 14054
-877243 607279
-61488 -541803
839910 -778520
498514 -990675
408344 758599
-596998 201097
-711216 615872
60...

output:

6
10
19
77
12
10
12
12
19
71
51
6
6
36
178
417
10
6
36
318
71
6
12
6
51
6
6
12
66
12
6
10
107
77
6
6
19
267
111
77
10
12
19
35
10
12
24
6
71
6
6
6
10
19
35
10
10
6
6
12
71
36
6
6
10
10
10
10
71
10
111
107
35
6
19
12
77
6
178
19
10
6
10
12
10
112
12
111
538
12
12
10
6
6
1807
66
6
10
12
12
10
12
6
12
...

result:

ok 200000 numbers

Test #12:

score: 4
Accepted
time: 697ms
memory: 40644kb

input:

200000 200000
492262 0
767261 0
-49558 0
763447 0
-766015 0
305219 0
216950 0
309815 0
-563799 0
-576993 0
807708 0
-28765 0
805496 0
-792510 0
452313 0
636912 0
251743 0
367464 0
460580 0
731290 0
-899643 0
35424 0
900164 0
-627830 0
-200278 0
-364485 0
85580 0
348513 0
-445170 0
782325 0
867546 0
...

output:

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

result:

ok 200000 numbers

Test #13:

score: 4
Accepted
time: 676ms
memory: 45012kb

input:

200000 200000
547911 0
477311 0
650541 0
-105453 0
626756 0
-374148 0
-185598 0
-740854 0
845506 0
692548 0
-87545 0
-338111 0
-672163 0
348336 0
790086 0
588112 0
874537 0
-165894 0
602594 0
-951962 0
121709 0
597190 0
-231436 0
954727 0
874009 0
923477 0
176425 0
-953583 0
107836 0
-354119 0
80494...

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 200000 numbers

Test #14:

score: 4
Accepted
time: 793ms
memory: 45664kb

input:

200000 200000
-317746997 0
-151278487 0
231239102 0
-333682162 0
817071806 0
778079717 0
-29317929 0
-796844681 0
-969298078 0
-290624098 0
-687507332 0
967855359 0
-200682268 0
446953365 0
829160344 0
431722814 0
-321478842 0
500793767 0
-958916933 0
-993173724 0
-583938136 0
-621654506 0
540155031...

output:

0
75
0
13
15
0
7
0
0
5471
0
0
0
0
2
32
1
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
7
0
0
0
0
0
0
0
28
0
0
0
0
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
85
0
3
9
0
0
0
0
0
8
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
13
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
87
0
0
1
0
0
0
0
0
0
29
5
0
101976
0
0
5
0
0
0
7...

result:

ok 200000 numbers

Test #15:

score: 4
Accepted
time: 88ms
memory: 165172kb

input:

2000 1000000
600102029 78163345
623529642 -781629210
-194743627 856505922
132730843 -866898111
496967234 357290802
424803615 -817449125
326888043 973054140
682875209 743038131
659124372 893679753
-415512262 835204413
-753019068 -821982592
650486625 656222368
765610921 -158965479
-131326155 454415998...

output:

3681425
3248740
8287314
3248740
2994042
2591533
10623830
2994042
55536188
3248740
2591533
181013291
2591533
2591533
3248740
9585148
4922188
4587911
2591533
3248740
2994042
2994042
8443551
681466
21601433
2591533
2994042
2994042
2591533
2591533
681466
2591533
681466
3248740
681466
23886441
2994042
45...

result:

ok 1000000 numbers

Test #16:

score: 4
Accepted
time: 111ms
memory: 252564kb

input:

2000 1000000
172304227 0
104292738 0
-257051223 0
-21999534 0
-574879748 0
-574439539 0
-947027598 0
765205348 0
195088335 0
406074782 0
75136395 0
227990070 0
900067610 0
675451839 0
804606264 0
556516588 0
-511265459 0
510580926 0
863647316 0
807267358 0
-778168632 0
127848817 0
255183075 0
-60073...

output:

169
993
169
98
12442
10743
736
10743
736
12442
12442
993
993
2714
736
98
27403
736
12442
1624037
98
993
10743
736
12442
10743
98
19028
736
736
2714
12442
173
993
2714
169
2714
76324
116236
736
2714
173
993
993
993
10743
10743
10743
993
307731
993
98
98
2714
993
99994
72535
98
736
736
12442
736
13587...

result:

ok 1000000 numbers

Test #17:

score: 4
Accepted
time: 673ms
memory: 55192kb

input:

1000000 10
156999516 -24390575
-347759760 638897014
-102812461 325031686
668597244 262829264
678216489 165516603
621656879 -412885032
233438419 931865318
709921083 -313209071
389603839 76036576
-769757796 359645480
-100357260 928717563
709905946 839359128
233518030 -695740543
524417586 -804059937
-4...

output:

6232
1308
13064
2742
1308
24817
2742
10027
15715
2742

result:

ok 10 numbers

Test #18:

score: 4
Accepted
time: 693ms
memory: 53376kb

input:

1000000 10
281115 207197
-791397 227390
-769663 849805
-689936 477469
-251524 174662
189816 721806
-579178 -339234
993809 -705268
-690664 35222
-298116 -663820
-321165 -327572
-609151 166540
799070 -156124
-305786 89239
53446 -399972
845917 137485
316083 266638
-720291 -915315
-706115 135108
-161326...

output:

152
3
7
3
3
7
21
6
62
5

result:

ok 10 numbers

Test #19:

score: 4
Accepted
time: 752ms
memory: 53364kb

input:

1000000 10
370517413 0
607064501 0
198217472 0
143369676 0
627031881 0
-242777381 0
-122948696 0
334651705 0
754835147 0
-975826131 0
-3570204 0
136544599 0
519231560 0
-21309928 0
-647797468 0
728822996 0
-239842256 0
854368498 0
-555223024 0
-177243458 0
-606866771 0
867321201 0
983555681 0
753390...

output:

0
2
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #20:

score: 0
Time Limit Exceeded

input:

1000000 1000000
-565158168 192228664
-60734026 -876227887
169956757 458933534
415705153 359751682
706646043 -267237804
-785235125 -286053701
-810363619 -883277015
-917766646 796218920
568429513 157525175
652148934 -563141041
101229780 387951397
138582181 234580165
989042915 303473055
848403115 67207...

output:


result:


Test #21:

score: 0
Time Limit Exceeded

input:

1000000 1000000
937028 -142721
470057 -596447
805603 -653737
422827 -146839
-134461 -284129
-740611 -822073
129788 -760939
189012 76048
-649576 825583
376935 955180
-675052 -614100
217445 -951905
463589 -489265
309830 -722532
510085 591599
-961137 67299
-817170 188112
338633 -558591
-571501 -205785
...

output:


result:


Test #22:

score: 0
Time Limit Exceeded

input:

1000000 1000000
556639 -726845
488045 -320786
907001 -483744
941440 533716
-722534 856343
-338618 616639
491388 733720
-416677 107094
108121 465292
-123127 350855
657412 326868
-943626 -335813
-502533 257525
56288 -494808
-248448 -317412
463444 -822305
686331 178764
-255923 18808
-520494 -446761
624...

output:

2
1
1
1
5
1
1
2
1
1
5
1
5
2
14
1
1
1
1
2
22
36
5
1
1
1
1
1
5
212
19
22
1
2
1
5
3
1
1
22
1
1
5
1
1
5
1
9
5
11
5
1
1
2
5
1
11
1
19
1
11
2
5
1
1
19
1
1
1
1
1
5
2
5
1
1
1
1
1
9
1
1
1
1
5
1
2
5
1
340
1
1
1
1
9
1
1
14
1
1
1
1
5
1
5
1
1
1
14
1
2
1
3
5
1
3
9
2
1
9
11
1
1
5
1
1
1
1
2
9
1
5
1
1
2
5
2
1
9
19
5...

result:


Test #23:

score: 0
Time Limit Exceeded

input:

1000000 1000000
-542377 0
80556 0
-734137 0
-588964 0
255112 0
598605 0
-363464 0
-703421 0
157594 0
-98285 0
799038 0
897889 0
-518690 0
-303647 0
-503359 0
166055 0
-173378 0
568761 0
-839895 0
-125384 0
-113615 0
-926581 0
-597497 0
865459 0
271137 0
779200 0
-589752 0
695449 0
-633220 0
477974 0...

output:


result:


Test #24:

score: 0
Time Limit Exceeded

input:

1000000 1000000
475716 0
733854 0
-670602 0
-495883 0
879413 0
-549166 0
395637 0
-922358 0
-95497 0
261093 0
-855001 0
-232761 0
839785 0
415412 0
456189 0
487755 0
951642 0
68750 0
-207887 0
108335 0
73919 0
-829879 0
-521857 0
-235996 0
-474559 0
50128 0
599195 0
-72168 0
454461 0
384522 0
-27507...

output:


result:


Test #25:

score: 0
Time Limit Exceeded

input:

1000000 1000000
-647194312 0
923266193 0
311967052 0
26202656 0
145325407 0
-363221031 0
322109698 0
400374410 0
-666477923 0
-803868087 0
-739610118 0
941620833 0
335162000 0
-343764277 0
-854360295 0
354763517 0
-559596318 0
-857042621 0
638986823 0
-794261929 0
137855671 0
317157550 0
942335473 0...

output:


result: