QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#423122 | #8179. 2D Parentheses | jr_linys | WA | 430ms | 39004kb | C++14 | 2.6kb | 2024-05-27 21:13:00 | 2024-05-27 21:13:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int> T read(){
char c;bool f=1;
while(!isdigit(c=getchar())) if(c=='-') f=0;
T x=c^'0';
while(isdigit(c=getchar())) x=x*10+(c^'0');
return f?x:-x;
}
template<class T>void Min(T &a,T b){if(b<a) a=b;}
template<class T>void Max(T &a,T b){if(b>a) a=b;}
const int N=200000;
int n,ans[N+5];
struct Dot{
int x,y,id;
}a[N+5],b[N+5];
struct cmp{
bool operator()(int u,int v)const{
return a[u].x<a[v].x||(a[u].x==a[v].x&&a[u].y<a[v].y);
}
};
set<int,cmp> T;
unsigned int t[N*8],ta[N*8];
bool vis[N*8];
inline void pushup(int p){
t[p]=max(t[p<<1],t[p<<1|1])+ta[p];
}
void upd(int p,int l,int r,int x,int y,int d){
if(x<=l&&r<=y) return t[p]+=d,ta[p]+=d,void();
int mid=(l+r)>>1;
if(x<=mid) upd(p<<1,l,mid,x,y,d);
if(y>mid) upd(p<<1|1,mid+1,r,x,y,d);
pushup(p);
}
int qry(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) return t[p];
int mid=(l+r)>>1,ans=0;
if(x<=mid) Max(ans,qry(p<<1,l,mid,x,y));
if(y>mid) Max(ans,qry(p<<1|1,mid+1,r,x,y));
return ans+ta[p];
}
int lineCnt,w[N+5];
struct Line{
int l,r,val,id;
};
vector<Line> v;
signed main(){
{//预处理
static int un[N*2+5];
n=read();
for(int i=1;i<=n;++i) a[i]={read(),read(),i};
for(int i=1;i<=n;++i) b[i]={read(),read(),i};
auto get=[](int &x){x=lower_bound(un+1,un+1+n*2,x)-un;};
for(int i=1;i<=n;++i) un[i]=a[i].x,un[i+n]=b[i].x;
sort(un+1,un+1+n*2);
for(int i=1;i<=n;++i) get(a[i].x),get(b[i].x);
for(int i=1;i<=n;++i) un[i]=a[i].y,un[i+n]=b[i].y;
sort(un+1,un+1+n*2);
for(int i=1;i<=n;++i) get(a[i].y),get(b[i].y);
}
sort(a+1,a+1+n,[](Dot a,Dot b){return a.y<b.y||(a.y==b.y&&a.x<b.x);});
sort(b+1,b+1+n,[](Dot a,Dot b){return a.y<b.y||(a.y==b.y&&a.x<b.x);});
for(int i=1,j=1;i<=n;++i){
while(j<=n&&a[j].y<b[i].y) T.insert(j),++j;
a[0]={b[i].x-1,b[i].y};
if(T.empty()){cout<<"No";return 0;}
auto it=T.lower_bound(0);
if(it==T.begin()){cout<<"No";return 0;}
--it;
int k=*it;T.erase(it);
ans[a[k].id]=b[i].id;
++lineCnt;
v.push_back({a[k].x,b[i].x-1,a[k].y,lineCnt});
v.push_back({a[k].x,b[i].x-1,b[i].y,-lineCnt});
}
sort(v.begin(),v.end(),[](Line a,Line b){
if(a.val!=b.val) return a.val<b.val;
if((a.id>0)!=(b.id>0)) return a.id<b.id;
if(a.id>0) return a.r-a.l>b.r-b.l;
return a.r-a.l<b.r-b.l;
});
for(auto [l,r,val,id]:v){
if(id>0){
w[id]=qry(1,1,n*2,l,r);
upd(1,1,n*2,l,r,1);
}else{
upd(1,1,n*2,l,r,-1);
if(qry(1,1,n*2,l,r)!=w[-id]){cout<<"No";return 0;}
}
}
cout<<"Yes\n";
for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9852kb
input:
3 0 0 2 -2 1 1 2 2 3 1 2 3
output:
Yes 3 2 1
result:
ok answer is YES, 3 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 9800kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 1ms
memory: 9792kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: 0
Accepted
time: 415ms
memory: 28060kb
input:
199996 94702923 895749121 -830347683 823853414 -638337012 -528381915 774504965 -903560893 465975432 931026841 47062323 901390864 539345338 830099354 278774201 896803047 -445303873 568413124 80473317 828648317 804283391 -307873779 543648687 893783688 814084625 -664894626 169476937 -999435847 -8232728...
output:
Yes 21701 88398 59327 146960 29196 103293 198434 198023 157367 48765 157321 148908 80650 112519 196489 172199 173973 5551 141927 136548 134111 182366 59175 165032 163355 57765 5843 31857 130090 185365 76890 97333 133685 142517 167272 4006 171963 1988 107334 183071 65560 70618 199137 151179 183975 10...
result:
ok answer is YES, 199996 tokens
Test #5:
score: 0
Accepted
time: 418ms
memory: 29332kb
input:
199989 -185038489 939943355 404432727 -854751373 554853823 193640691 301504969 -998071590 274900356 938454158 -432464517 285421885 405518801 -987371480 571222708 909692099 -759427030 -999520045 869336666 847296633 -622724138 -999895334 -54035108 -876650516 453457981 -842759465 892363710 -794270574 1...
output:
Yes 29051 42308 37337 84855 166499 109338 34862 199409 32310 182823 20620 177599 116234 29219 168881 98498 20908 64603 145113 95741 106479 41666 136146 57568 153800 159627 73275 187439 74915 2272 25123 152755 131852 155786 59824 193752 26923 55748 13026 132594 87769 26528 189799 148030 136086 143680...
result:
ok answer is YES, 199989 tokens
Test #6:
score: 0
Accepted
time: 430ms
memory: 29392kb
input:
199991 -900159443 -671207779 -114175529 -885513466 -57386301 392144414 623068349 -990207451 -466916252 -379159070 -390577839 868367620 -142964637 -583431492 -288979694 -899596387 -357113786 867092775 833205097 992058046 -885274285 951889875 -406261261 872434960 -99080436 889619788 -37516399 -2293017...
output:
Yes 3275 63270 93912 127141 22479 165152 198171 26948 80966 36189 160851 192441 14819 41768 118467 117142 19608 136232 104951 109409 47223 99091 151706 110331 54762 66016 16120 166582 89823 77684 49744 74404 47622 182252 83554 97967 190281 111679 20281 17322 79190 103090 116209 40445 137659 13013 24...
result:
ok answer is YES, 199991 tokens
Test #7:
score: 0
Accepted
time: 425ms
memory: 28116kb
input:
199987 -46649274 139363612 803504473 -487067218 -231304341 961630672 807256898 -256192650 -473216529 -412520640 387331113 961360032 -718008950 -1000000000 156200839 95571209 981893716 -29439313 -470730442 -783533869 799296462 104576693 -553698761 -906790634 807374303 -24023479 309903544 968199523 32...
output:
Yes 108253 39856 69761 52978 95487 52526 165960 5834 154779 176120 98055 116863 185474 199758 158834 7618 59391 94556 148087 135584 103212 46150 11774 57061 193721 73508 53857 107232 28635 11110 92043 112059 176064 91995 182180 157770 164760 94634 170392 57167 64585 147769 177684 141597 196364 5163 ...
result:
ok answer is YES, 199987 tokens
Test #8:
score: 0
Accepted
time: 424ms
memory: 25832kb
input:
199998 520404957 315206955 589123511 -430859516 376860728 -987316121 614664700 -301663049 978007244 -969619964 636107820 259251657 137671843 -958442271 549117430 -935982467 341044573 -957188402 920491566 768041266 584917074 -822386658 170473403 -165076605 528955497 239159653 608627148 -761435336 294...
output:
Yes 82347 108348 69489 26272 38797 5634 171949 36739 168135 91411 33031 55676 52141 104041 168253 25828 64027 133931 106943 41392 145594 100287 149043 92143 168786 81236 24112 157854 150937 77525 2953 98374 15882 5118 86665 187254 96225 44878 26976 116891 140926 67595 136505 12406 158887 133562 1802...
result:
ok answer is YES, 199998 tokens
Test #9:
score: 0
Accepted
time: 286ms
memory: 26160kb
input:
199993 -751151977 -533994506 -927773836 -32372872 56850331 -243441225 327514682 -361038889 247003430 -838950588 -981662694 -566754857 -57613101 -102410474 857750386 -993733474 184906291 -664905204 -479853877 -891755682 851112690 -967524478 -597827988 -230528151 -782058930 -309016717 684473363 -93368...
output:
No
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 295ms
memory: 26588kb
input:
199995 -88045160 -754166053 537999118 -600975136 507992830 -518080636 39365554 -358691055 -758317392 512499723 881007532 -962828746 -572412035 175565135 968490041 -994664833 709978672 -804735716 -303634784 -694082713 -59130173 -558086683 134566179 -468537576 -559886570 -13279147 956873077 -987380660...
output:
No
result:
ok answer is NO
Test #11:
score: 0
Accepted
time: 281ms
memory: 26740kb
input:
199995 751877273 -902803580 -438283469 -133229905 -457924536 -954675359 838836144 -929871820 -239512796 222101817 563268330 -660190100 556870083 -946184789 -985201972 66353356 -216346975 -313862155 559918674 -947158712 192980719 -961438929 -811651008 -161707407 284585611 -661800796 -414734311 360692...
output:
No
result:
ok answer is NO
Test #12:
score: 0
Accepted
time: 286ms
memory: 26004kb
input:
199992 467672870 -996993001 241650219 -493925971 849648842 -892593087 -326147502 -692396432 -866805696 -775049492 -380985862 -92370469 -362825862 -317436226 830242906 -846790011 -40608016 -941933328 144908937 -471622120 -396018063 -236727104 47294885 -81681580 698568506 -862960919 447264189 -5301740...
output:
No
result:
ok answer is NO
Test #13:
score: 0
Accepted
time: 391ms
memory: 28280kb
input:
199991 109672170 573860547 546933098 -90570193 928277586 970298066 987599431 968626012 920336525 353233135 454572949 967884727 421362358 995209255 598417779 969960580 106017730 762424678 543974354 -684869086 121816039 648191189 380803651 636788977 -956413035 -999893957 473169616 349122663 406717571 ...
output:
No
result:
ok answer is NO
Test #14:
score: 0
Accepted
time: 398ms
memory: 29260kb
input:
200000 12292352 -455065141 -390181101 -783347162 156602165 802988410 743295114 -667798048 375893047 -358589847 115224102 -483640155 979452678 -186641379 -774888997 600180205 226761733 665391746 993091639 -152845106 -954202769 -389817917 668939766 -197604121 657174588 -454213306 -657711838 122038041 ...
output:
No
result:
ok answer is NO
Test #15:
score: 0
Accepted
time: 401ms
memory: 37208kb
input:
199997 -999879824 -999879824 -999985274 -999985274 -999905148 -999905148 -999992386 -999992387 -999859308 -999859309 -999871546 -999871546 -999805065 -999805065 -999975361 -999975361 -999862311 -999862312 -999801098 -999801098 -999979435 -999979436 -999843402 -999843402 -999949497 -999949496 -999921...
output:
Yes 106277 155047 5259 13342 13281 15642 84131 172847 53049 43993 110374 24134 69229 82585 137484 87547 22101 194260 112249 78479 57485 118277 93747 49494 79728 32881 180798 114485 105611 133291 92516 2059 40150 191984 108774 151002 106618 25201 196204 157334 118866 41981 73562 38499 193789 191176 6...
result:
ok answer is YES, 199997 tokens
Test #16:
score: 0
Accepted
time: 397ms
memory: 39004kb
input:
199981 -999868018 -999868018 -999964060 -999964060 -999895225 -999895226 -999868368 -999868368 -999839616 -999839615 -999873455 -999873455 -999859804 -999859803 -999861087 -999861087 -999940826 -999940826 -999906591 -999906590 -999855890 -999855890 -999978359 -999978359 -999821571 -999821570 -999943...
output:
Yes 97200 167575 94367 147836 84642 186962 186483 97271 60515 10785 92661 159707 122996 89145 61642 185036 111235 182354 172420 180889 137780 196273 68284 68008 195923 134210 136528 70464 52625 101192 146980 109825 77820 168411 163267 26971 163506 38993 174992 166277 126904 98713 175260 187079 11642...
result:
ok answer is YES, 199981 tokens
Test #17:
score: 0
Accepted
time: 410ms
memory: 37512kb
input:
199982 -999912098 -999912098 -999829986 -999829985 -999940273 -999940272 -999970088 -999970089 -999809633 -999809632 -999888323 -999888323 -999904094 -999904095 -999923920 -999923920 -999931411 -999931412 -999880937 -999880936 -999883720 -999883721 -999982089 -999982090 -999820997 -999820998 -999931...
output:
Yes 149529 161836 176627 121589 167251 152322 135802 154990 159242 70441 56257 40831 101222 145107 14227 62671 115393 153960 76112 38412 48671 10743 75279 170041 56890 95495 122455 127520 105472 148556 67955 8183 133209 126551 159409 90942 77523 78648 127222 110208 44715 178187 166612 70744 47447 19...
result:
ok answer is YES, 199982 tokens
Test #18:
score: 0
Accepted
time: 308ms
memory: 36444kb
input:
199998 -999887284 -999887283 -999915363 -999915362 -999823075 -999823075 -999863682 -999863681 -999859733 -999859734 -999956745 -999956744 -999997944 -999997944 -999847489 -999847488 -999857822 -999857823 -999852823 -999852823 -999839707 -999839708 -999930996 -999930996 -999975227 -999975227 -999825...
output:
No
result:
ok answer is NO
Test #19:
score: 0
Accepted
time: 319ms
memory: 38304kb
input:
199994 -999912996 -999912997 -999836568 -999836567 -999883073 -999883074 -999996147 -999996146 -999825382 -999825381 -999985933 -999985934 -999982238 -999982239 -999869626 -999869625 -999975304 -999975303 -999823144 -999823144 -999969948 -999969947 -999904042 -999904041 -999933436 -999933436 -999803...
output:
No
result:
ok answer is NO
Test #20:
score: 0
Accepted
time: 313ms
memory: 38276kb
input:
199992 -999972333 -999972334 -999891982 -999891983 -999882809 -999882810 -999822804 -999822803 -999967743 -999967744 -999983993 -999983993 -999863753 -999863752 -999884515 -999884514 -999888863 -999888863 -999885971 -999885971 -999984941 -999984941 -999913751 -999913752 -999960346 -999960347 -999921...
output:
No
result:
ok answer is NO
Test #21:
score: 0
Accepted
time: 302ms
memory: 27728kb
input:
199997 -122202317 112267336 778900868 -580844804 613370701 -764480327 935405236 -986111739 707512416 -854652106 -946807516 -924919586 -284367953 -995688300 488682605 -640251254 360488164 -8716950 447222586 -622186429 486121949 -335591140 60499929 578932647 467103249 -651090790 935758219 -461652795 3...
output:
No
result:
ok answer is NO
Test #22:
score: 0
Accepted
time: 312ms
memory: 28728kb
input:
199983 -561079724 818030313 223496748 263930967 -920520777 944819218 -781859731 955980363 230356676 996890160 -653304277 999787369 -574413094 997581938 -670597993 840688725 -996811195 887239661 -931872992 -771635999 -206187418 868462755 -324784222 868831033 490889005 976071729 -798799305 -994557939 ...
output:
No
result:
ok answer is NO
Test #23:
score: 0
Accepted
time: 323ms
memory: 27848kb
input:
199991 522585641 -54228408 -612804158 -931880027 835863190 -746008723 917559328 -26673058 977631684 -579078012 958896264 269727428 612182590 970041243 995860183 -558049114 -994388586 -917944975 463835784 844964192 979790893 -819275646 998649245 -567734525 922097604 947459660 -90489889 868756734 -401...
output:
No
result:
ok answer is NO
Test #24:
score: 0
Accepted
time: 334ms
memory: 27696kb
input:
199997 108546236 744538874 623931335 503758282 -856923870 -342916607 -452521388 853267479 737136515 803101336 660251162 577444293 -88043309 711307234 -957687754 -304875237 -975000984 342903552 815991558 580088695 516821560 47309582 645428571 528996479 -8631341 569902320 471896506 999228112 -83557659...
output:
No
result:
ok answer is NO
Test #25:
score: 0
Accepted
time: 316ms
memory: 27548kb
input:
199996 214657871 545155159 -471738265 977059933 -501095668 -581526840 -638594572 781399506 838465777 -497260622 -434327766 324377615 -974334969 289339756 579268895 259485230 -323777384 988668418 -855653709 -649586884 575625801 517530062 -356437053 -584077742 -484872296 765519230 22206394 -150520145 ...
output:
No
result:
ok answer is NO
Test #26:
score: -100
Wrong Answer
time: 416ms
memory: 28540kb
input:
199999 -240535554 -421679319 -905108512 -666141640 -785476573 572798433 -480315216 557644077 -791990949 577248627 -668916644 -769003399 -792952592 277657199 -483495235 401600554 -460111143 616819036 -484228813 -10463553 766448353 -119248395 -819970967 517340196 -812374957 176095128 -501090445 560006...
output:
Yes 144295 130731 122385 83862 182311 152086 23249 85363 22674 123802 152971 173569 88934 182538 10409 160618 199228 68475 130511 140535 27769 105308 184715 80513 10404 128370 45950 11097 65587 27532 199642 44130 5153 118704 37329 145514 149868 115525 131355 97191 23030 141433 92165 188954 95942 160...
result:
wrong answer expected NO, found YES