QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423142#8179. 2D ParenthesescomplexorWA 192ms33048kbC++232.9kb2024-05-27 21:17:092024-05-27 21:17:09

Judging History

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

  • [2024-05-27 21:17:09]
  • 评测
  • 测评结果:WA
  • 用时:192ms
  • 内存:33048kb
  • [2024-05-27 21:17:09]
  • 提交

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;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 16116kb

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: 2ms
memory: 11800kb

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

input:

1
1 1
0 0

output:

NO

result:

ok answer is NO

Test #4:

score: 0
Accepted
time: 150ms
memory: 26104kb

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: 137ms
memory: 26500kb

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: 140ms
memory: 26068kb

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: 139ms
memory: 26048kb

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

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

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:

Yes
75898
27981
63116
76731
46674
183792
5726
159225
91627
83677
161737
19456
171828
12886
61567
134496
51885
15970
81343
80579
130000
117728
19235
186117
46048
172751
92445
142419
58364
178578
177050
144878
137398
116654
75072
45601
109641
109066
1961
151046
199903
33486
61640
157845
18128
154580
4...

result:

wrong answer expected NO, found YES