QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #718531 | #9613. 计算几何 | cyz2010 | 40 | 3956ms | 96004kb | C++14 | 2.7kb | 2024-11-06 20:45:34 | 2024-11-06 20:45:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
const int yyj=1e9,inf=2e9;
#define eb emplace_back
int n,Q;
int m,b[N],nw[N];
struct Point{int x,y,z;}a[N];
vector<Point>qq;
namespace SGT
{
#define PII pair<int,int>
PII t1[N<<2],t2[N<<2];
inline PII gmin(PII x,PII y){return x.first<y.first?x:y;}
void build(int p,int l,int r)
{
t1[p]=t2[p]={inf,0};
if(l==r) return ;
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
inline void push_up(int p)
{
t1[p]=gmin(t1[p<<1],t1[p<<1|1]);
t2[p]=gmin(t2[p<<1],t2[p<<1|1]);
}
void update(int p,int l,int r,int x,int y,int z,int pos)
{
if(l==r) return t1[p]={-y-z,pos},t2[p]={-y+z,pos},void();
int mid=(l+r)>>1;
if(x<=mid) update(p<<1,l,mid,x,y,z,pos);
else update(p<<1|1,mid+1,r,x,y,z,pos);
push_up(p);
}
void clr(int p,int l,int r,int x)
{
t1[p]=t2[p]={inf,0};
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) clr(p<<1,l,mid,x);
else clr(p<<1|1,mid+1,r,x);
}
PII query1(int p,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return t1[p];
int mid=(l+r)>>1;PII ret={inf,0};
if(x<=mid) ret=gmin(ret,query1(p<<1,l,mid,x,y));
if(y>mid) ret=gmin(ret,query1(p<<1|1,mid+1,r,x,y));
return ret;
}
PII query2(int p,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return t2[p];
int mid=(l+r)>>1;PII ret={inf,0};
if(x<=mid) ret=gmin(ret,query2(p<<1,l,mid,x,y));
if(y>mid) ret=gmin(ret,query2(p<<1|1,mid+1,r,x,y));
return ret;
}
}using namespace SGT;
int ans[N];
vector<Point>c;
void solve(int l,int r,vector<Point>q)
{
if(l>=r||q.empty()) return ;
int ret=inf,u=0,v=0;
for(int i=l;i<=r;i++) c.eb(a[i]);
sort(c.begin(),c.end(),[&](Point x,Point y){return x.x<y.x;});
for(Point i:c)
{
int x=i.x,y=i.y,z=nw[i.z];
PII L=query1(1,1,m,1,z),R=query2(1,1,m,z,m);
L.first+=x+y;R.first+=x-y;L=gmin(L,R);
if(L.first<ret)
{
ret=L.first;
u=L.second;v=i.z;
}
update(1,1,m,z,x,y,i.z);
}
for(Point i:c)
clr(1,1,m,nw[i.z]);
c.clear();
// printf("l=%d r=%d u=%d v=%d ret=%d\n",l,r,u,v,ret);
vector<Point>q1,q2;
if(u>v) swap(u,v);
for(Point i:q)
{
if(i.x<=u&&i.y>=v)
ans[i.z]=ret;
else if(i.y<v)
q1.eb(i);
else
q2.eb(i);
}
solve(l,v-1,q1);
solve(u+1,r,q2);
}
int main()
{
// freopen("geo3.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
b[++m]=a[i].y;a[i].z=i;
}
sort(b+1,b+m+1);m=unique(b+1,b+m+1)-b-1;
for(int i=1;i<=n;i++) nw[i]=lower_bound(b+1,b+m+1,a[i].y)-b;
for(int i=1;i<=Q;i++)
{
int x,y;scanf("%d%d",&x,&y);
qq.eb((Point){x,y,i});
}
build(1,1,m);
solve(1,n,qq);
for(int i=1;i<=Q;i++)
printf("%d\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Time Limit Exceeded
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:
result:
Test #2:
score: 4
Accepted
time: 0ms
memory: 14188kb
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: 0
Time Limit Exceeded
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:
result:
Test #4:
score: 4
Accepted
time: 417ms
memory: 15136kb
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: 468ms
memory: 16936kb
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: 48ms
memory: 15100kb
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: 42ms
memory: 14832kb
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: 45ms
memory: 16712kb
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: 0
Time Limit Exceeded
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:
result:
Test #10:
score: 0
Time Limit Exceeded
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:
result:
Test #11:
score: 0
Time Limit Exceeded
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:
result:
Test #12:
score: 4
Accepted
time: 595ms
memory: 35416kb
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: 563ms
memory: 32976kb
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: 0
Time Limit Exceeded
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:
result:
Test #15:
score: 0
Time Limit Exceeded
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:
result:
Test #16:
score: 0
Memory Limit Exceeded
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:
result:
Test #17:
score: 0
Time Limit Exceeded
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:
result:
Test #18:
score: 0
Time Limit Exceeded
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:
result:
Test #19:
score: 4
Accepted
time: 850ms
memory: 43180kb
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:
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
Test #24:
score: 4
Accepted
time: 3956ms
memory: 96004kb
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 1000000 numbers
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:
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 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 11 0 0 1916 0 0 0 0 0 0 27 0 7 0 0 0 0 205 0 0 0 88 0 0 0 ...