QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423165#8179. 2D Parenthesesjr_linysWA 419ms40672kbC++142.8kb2024-05-27 21:22:272024-05-27 21:22:28

Judging History

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

  • [2024-05-27 21:22:28]
  • 评测
  • 测评结果:WA
  • 用时:419ms
  • 内存:40672kb
  • [2024-05-27 21:22:27]
  • 提交

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],g[N+5],h[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});
		g[lineCnt]=a[k].y;
		h[lineCnt]=b[i].y;
	}
	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){
			if(h[a.id]!=h[b.id]) return h[a.id]>h[b.id];
			return a.l<b.l;
		}
		if(g[-a.id]!=g[-b.id]) return g[-a.id]>g[-b.id];
		return a.l>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: 9756kb

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: 0ms
memory: 11784kb

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: 0
Accepted
time: 413ms
memory: 29856kb

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

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: 404ms
memory: 29420kb

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: 417ms
memory: 31148kb

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: 410ms
memory: 31200kb

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: 280ms
memory: 24592kb

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: 288ms
memory: 27096kb

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: 302ms
memory: 29456kb

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: 300ms
memory: 24556kb

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: 389ms
memory: 28528kb

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: 403ms
memory: 30760kb

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: 400ms
memory: 39732kb

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: 414ms
memory: 39736kb

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: 419ms
memory: 40672kb

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: 309ms
memory: 36884kb

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: 323ms
memory: 39012kb

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: 318ms
memory: 39112kb

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: 306ms
memory: 30536kb

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: 318ms
memory: 30940kb

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: 340ms
memory: 30816kb

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: 342ms
memory: 30644kb

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: 336ms
memory: 28952kb

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: 398ms
memory: 30756kb

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