QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423168 | #8179. 2D Parentheses | complexor | WA | 103ms | 24860kb | C++23 | 2.9kb | 2024-05-27 21:23:27 | 2024-05-27 21:23:27 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, int> pii;
#define MP std::make_pair
#define fi first
#define se second
int read()
{
int s = 0, f = 1;
char c = getchar();
while (!(c >= '0' && c <= '9'))
f ^= (c == '-'), c = getchar();
while (c >= '0' && c <= '9')
s = s * 10 + (c ^ 48), c = getchar();
return f ? s : -s;
}
const int MAXN = 400005;
struct Tuple
{
int x, y, z;
Tuple(int _x = 0, int _y = 0, int _z = 0)
: x(_x), y(_y), z(_z){}
friend bool operator<(Tuple t1, Tuple t2)
{ return t1.x != t2.x ? t1.x < t2.x : t1.y != t2.y ? t1.y < t2.y : t1.z < t2.z; }
} ;
struct Segment
{
int x, yl, yr, v;
Segment(){}
Segment(int _x, int _yl, int _yr, int _v)
: x(_x), yl(_yl), yr(_yr), v(_v) {}
} sg[MAXN << 1];
std::set<Tuple> rec;
int n, ans[MAXN], m = 0, yy[MAXN << 1], V;
int ida[MAXN], idb[MAXN];
pii a[MAXN], b[MAXN];
namespace BIT
{
int c[MAXN << 1] = {0};
void modify(int x, int v)
{
for (; x <= V; x += x & -x)
c[x] += v;
}
int query(int x)
{
int res = 0;
for (; x; x -= x & -x)
res += c[x];
return res;
}
int query(int l, int r) { return query(r) - query(l - 1); }
}
int getId(int y){ return std::lower_bound(yy + 1, yy + V + 1, y) - yy; }
int main()
{
n = read();
for (int i = 1; i <= n; i++) a[i].fi = read(), a[i].se = read();
for (int i = 1; i <= n; i++) b[i].fi = read(), b[i].se = read();
std::iota(ida + 1, ida + n + 1, 1);
std::iota(idb + 1, idb + n + 1, 1);
if (n <= 2) return printf("NO"), 0;
std::sort(ida + 1, ida + n + 1, [](int i, int j){ return a[i] > a[j]; });
std::sort(idb + 1, idb + n + 1, [](int i, int j){ return b[i] > b[j]; });
for (int i = 1, j = 1; i <= n; i++)
{
for (; j <= n && b[idb[j]].fi > a[ida[i]].fi; j++)
rec.emplace(b[idb[j]].se, b[idb[j]].fi, idb[j]);
auto it = rec.lower_bound(Tuple(a[ida[i]].se + 1, -1e9 - 1, 0));
if (it == rec.end()) return printf("No\n"), 0;
ans[ida[i]] = it->z;
yy[++V] = a[ida[i]].se, yy[++V] = it->x;
sg[++m] = Segment(a[ida[i]].fi, a[ida[i]].se, it->x, 1);
sg[++m] = Segment(it->y + 1, a[ida[i]].se, it->x, -1);
rec.erase(it);
}
V = std::unique(yy + 1, yy + n * 2 + 1) - yy - 1;
std::sort(sg + 1, sg + m + 1, [](Segment a, Segment b){
if (a.x == b.x && a.v == b.v)
return a.v == -1 ? a.yr - a.yl < b.yr - b.yl : a.yr - a.yl > b.yr - b.yl;
return a.x == b.x ? a.v < b.v : a.x < b.x;
});
for (int i = 1; i <= m; i++)
{
int l = getId(sg[i].yl), r = getId(sg[i].yr);
// printf("%d: %d %d %d %d %d\n", i, sg[i].x, sg[i].yl, sg[i].yr, sg[i].v, BIT::query(l + 1, r - 1));
if (sg[i].v == 1 && BIT::query(l + 1, r - 1) > 0)
return printf("No"), 0;
if (sg[i].v == -1 && BIT::query(l + 1, r - 1) > 0)
return printf("No\n"), 0;
BIT::modify(l, sg[i].v), BIT::modify(r, sg[i].v);
}
printf("Yes\n");
for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 14064kb
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: 2ms
memory: 13944kb
input:
2 1 0 0 1 2 3 3 2
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 2ms
memory: 11804kb
input:
1 1 1 0 0
output:
NO
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 103ms
memory: 24860kb
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