QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423147#8179. 2D ParenthesescomplexorWA 170ms39256kbC++232.9kb2024-05-27 21:18:082024-05-27 21:18:08

Judging History

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

  • [2024-05-27 21:18:08]
  • 评测
  • 测评结果:WA
  • 用时:170ms
  • 内存:39256kb
  • [2024-05-27 21:18:08]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, int> pii;
#define MP std::make_pair
#define fi first
#define se second
int read()
{
	int s = 0, f = 1;
	char c = getchar();
	while (!(c >= '0' && c <= '9'))
		f ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9')
		s = s * 10 + (c ^ 48), c = getchar();
	return f ? s : -s;
}
const int MAXN = 400005;
struct Tuple 
{ 
	int x, y, z; 
	Tuple(int _x = 0, int _y = 0, int _z = 0)
	: x(_x), y(_y), z(_z){}
	friend bool operator<(Tuple t1, Tuple t2)
	{ return t1.x != t2.x ? t1.x < t2.x : t1.y != t2.y ? t1.y < t2.y : t1.z < t2.z; }
} ;
struct Segment
{
	int x, yl, yr, v;
	Segment(){}
	Segment(int _x, int _yl, int _yr, int _v)
	: x(_x), yl(_yl), yr(_yr), v(_v) {}
} sg[MAXN << 1];
std::set<Tuple> rec;
int n, ans[MAXN], m = 0, yy[MAXN << 1], V;
int ida[MAXN], idb[MAXN];
pii a[MAXN], b[MAXN];
namespace BIT
{
	int c[MAXN << 1] = {0};
	void modify(int x, int v)
	{
		for (; x <= V; x += x & -x)
			c[x] += v;
	}
	int query(int x)
	{
		int res = 0;
		for (; x; x -= x & -x)
			res += c[x];
		return res;
	}
	int query(int l, int r) { return query(r) - query(l - 1); }
}
int getId(int y){ return std::lower_bound(yy + 1, yy + V + 1, y) - yy; }
int main() 
{
	n = read();
	for (int i = 1; i <= n; i++) a[i].fi = read(), a[i].se = read();
	for (int i = 1; i <= n; i++) b[i].fi = read(), b[i].se = read();
	std::iota(ida + 1, ida + n + 1, 1);
	std::iota(idb + 1, idb + n + 1, 1);
	if (n <= 2) return printf("NO"), 0;
	std::sort(ida + 1, ida + n + 1, [](int i, int j){ return a[i] > a[j]; });
	std::sort(idb + 1, idb + n + 1, [](int i, int j){ return b[i] > b[j]; });
	for (int i = 1, j = 1; i <= n; i++)
	{
		for (; j <= n && b[idb[j]].fi > a[ida[i]].fi; j++)
			rec.emplace(b[idb[j]].se, b[idb[j]].fi, idb[j]);
		auto it = rec.lower_bound(Tuple(a[ida[i]].se + 1, -1e9 - 1, 0));
		if (it == rec.end()) return printf("No\n"), 0;
		ans[ida[i]] = it->z;
		yy[++V] = a[ida[i]].se, yy[++V] = it->x;
		sg[++m] = Segment(a[ida[i]].fi, a[ida[i]].se, it->x, 1);
		sg[++m] = Segment(it->y, a[ida[i]].se, it->x, -1);
		rec.erase(it);
	}
	V = std::unique(yy + 1, yy + n * 2 + 1) - yy - 1;
	std::sort(sg + 1, sg + m + 1, [](Segment a, Segment b){
		if (a.x == b.x && a.v == b.v)
			return a.v == -1 ? a.yr - a.yl < b.yr - b.yl : a.yr - a.yl > b.yr - b.yl;
		return a.x == b.x ? a.v < b.v : a.x < b.x;
	});
	for (int i = 1; i <= m; i++)
	{
		int l = getId(sg[i].yl), r = getId(sg[i].yr);
		// printf("%d: %d %d %d %d %d\n", i, sg[i].x, sg[i].yl, sg[i].yr, sg[i].v, BIT::query(l + 1, r - 1));
		if (sg[i].v == 1 && l < r && BIT::query(l + 1, r - 1) > 0)
			return printf("No"), 0;
		if (sg[i].v == -1 && l < r && BIT::query(l + 1, r - 1) > 0)
			return printf("No\n"), 0;
		BIT::modify(l, sg[i].v), BIT::modify(r, sg[i].v);
	}
	printf("Yes\n");
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 12032kb

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

input:

2
1 0
0 1
2 3
3 2

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 0ms
memory: 13984kb

input:

1
1 1
0 0

output:

NO

result:

ok answer is NO

Test #4:

score: 0
Accepted
time: 155ms
memory: 28652kb

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: 150ms
memory: 26152kb

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: 160ms
memory: 26100kb

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: 151ms
memory: 26544kb

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: 152ms
memory: 26556kb

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: 162ms
memory: 30440kb

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: 168ms
memory: 28824kb

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: 170ms
memory: 30900kb

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: 151ms
memory: 30508kb

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: 126ms
memory: 26464kb

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: 138ms
memory: 26536kb

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: 159ms
memory: 37140kb

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: 155ms
memory: 38580kb

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: 154ms
memory: 38592kb

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: -100
Wrong Answer
time: 151ms
memory: 39256kb

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:

Yes
142249
91344
45863
164356
71603
122948
168879
95005
6898
50618
137771
183954
87219
114731
56937
198904
70842
127009
183113
148328
14185
97936
188190
197559
8603
30409
158541
101883
193669
1476
4599
5119
135718
196242
133171
13500
146123
36815
108251
88253
40967
137665
185705
146043
136983
37304
...

result:

wrong answer expected NO, found YES