QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #718891 | #9613. 计算几何 | Akagi_shigeru | 76 | 826ms | 252564kb | C++23 | 1.8kb | 2024-11-06 21:42:33 | 2024-11-06 21:42:33 |
Judging History
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');
}
Details
Tip: Click on the bar to expand more detailed information
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...