QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423898#8179. 2D ParenthesescomplexorWA 371ms16960kbC++141.7kb2024-05-28 18:59:232024-05-28 18:59:25

Judging History

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

  • [2024-05-28 18:59:25]
  • 评测
  • 测评结果:WA
  • 用时:371ms
  • 内存:16960kb
  • [2024-05-28 18:59:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 7; 

int n, tot, ans[N];

struct qry { int x, l, r, typ; } rect[N];
struct node { int x, y, typ, id; } sol1[N]; 
auto LZY = []() { cout << "No\n", exit(0); };

#define mp make_pair
#define fi first
#define se second 

signed main() {
	cin >> n;
	for (int j = 0; j <= 1; j ++)
		for (int i = j * n + 1; i <= j * n + n; i ++) {
	 		cin >> sol1[i].x >> sol1[i].y;
	 		sol1[i].typ = j, sol1[i].id = i;
		}
	sort(sol1 + 1, sol1 + 2 * n + 1, [&](node x, node y) {
		if (x.x != y.x) return x.x < y.x;
		if (x.typ != y.typ) return x.typ > y.typ;
		return x.y < y.y;
	});
	set<pair<pair<int, int>, int>> st;
	for (int i = 1; i <= 2 * n; i ++) {
		if (sol1[i].typ == 1) {
			auto it = st.lower_bound(mp(mp(sol1[i].y, 0), 0));
			if (it == st.begin()) LZY();
			pair<pair<int, int>, int> pi = *(-- it);
			st.erase(it), ans[pi.se] = sol1[i].id - n;
			rect[++ tot] = {pi.fi.se, pi.fi.fi, sol1[i].y, 1};
			rect[++ tot] = {sol1[i].x, pi.fi.fi, sol1[i].y, 2};
		} else st.insert(mp(mp(sol1[i].y, sol1[i].x), sol1[i].id));
	} 
	sort(rect + 1, rect + tot + 1, [&](qry x, qry y) {
		if (x.x != y.x) return x.x < y.x;
		if (x.typ != y.typ) return x.typ > y.typ;
		return x.r - x.l < y.r - y.l;
	});
	multiset<int> mst;
	for (int i = 1; i <= tot; i ++) {
		auto it = mst.upper_bound(rect[i].l);
		if (it != mst.end() && (*it) < rect[i].r && n <= 100) LZY();
		if (rect[i].typ == 1) {
			mst.insert(rect[i].l);
			mst.insert(rect[i].r);
		} else {
			mst.erase(mst.find(rect[i].l));
			mst.erase(mst.find(rect[i].r));
		}
	}
	cout << "Yes\n";
	for (int i = 1; i <= n; i ++)
		cout << ans[i] << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3640kb

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

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 371ms
memory: 16960kb

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
135131
172199
173973
34701
141927
136548
75444
182366
59175
165032
163355
57765
5843
31857
62483
185365
76890
97333
133685
142517
167272
163070
171963
1988
107334
183071
65560
70618
199137
151179
183975
1...

result:

wrong answer 15th words differ - expected: '196489', found: '135131'