QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423890#8179. 2D ParenthesescomplexorWA 296ms16868kbC++141.7kb2024-05-28 18:54:562024-05-28 18:54:56

Judging History

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

  • [2024-05-28 18:54:56]
  • 评测
  • 测评结果:WA
  • 用时:296ms
  • 内存:16868kb
  • [2024-05-28 18:54:56]
  • 提交

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) 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: 7696kb

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

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 296ms
memory: 16868kb

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:

No

result:

wrong answer expected YES, found NO