QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423893#8179. 2D ParenthesescomplexorWA 372ms17088kbC++141.7kb2024-05-28 18:56:112024-05-28 18:56:12

Judging History

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

  • [2024-05-28 18:56:12]
  • 评测
  • 测评结果:WA
  • 用时:372ms
  • 内存:17088kb
  • [2024-05-28 18:56:11]
  • 提交

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, sol1[i].x), 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: 7700kb

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

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 372ms
memory: 17088kb

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
159482
29196
93486
188581
151588
157367
48765
151498
110651
137133
196363
135131
109982
173973
34701
141927
136548
75444
48198
59175
165032
74619
44935
5843
31857
62483
155862
182390
97333
145165
56089
167272
163070
115046
1988
107334
136611
65560
91317
199137
149107
10550
1018...

result:

wrong answer 4th words differ - expected: '146960', found: '159482'