QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423890 | #8179. 2D Parentheses | complexor | WA | 296ms | 16868kb | C++14 | 1.7kb | 2024-05-28 18:54:56 | 2024-05-28 18:54:56 |
Judging History
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