QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423893 | #8179. 2D Parentheses | complexor | WA | 372ms | 17088kb | C++14 | 1.7kb | 2024-05-28 18:56:11 | 2024-05-28 18:56:12 |
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 && 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'