QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422838 | #8179. 2D Parentheses | complexor | WA | 0ms | 9884kb | C++23 | 2.7kb | 2024-05-27 19:44:27 | 2024-05-27 19:44:28 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
typedef long long LL;
#define clr(a, n) memset(a, 0, sizeof(int) * (n))
#define cpy(a, b, n) memcpy(a, b, sizeof(int) * (n))
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 = 200005;
struct Point
{
int x, y, id, o;
friend bool operator<(Point a, Point b){ return a.x != b.x ? a.x < b.x : a.o < b.o; }
} p[MAXN << 1];
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<Point> rec;
int n, ans[MAXN], m = 0, yy[MAXN << 1], V;
namespace BIT
{
LL c[MAXN << 1] = {0};
void modify(int x, int v)
{
for (; x <= V; x += x & -x)
c[x] += v;
}
LL query(int x)
{
LL res = 0;
for (; x; x -= x & -x)
res += c[x];
return res;
}
LL 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; }
bool contain(Segment a, Segment b){ return (b.yl <= a.yl && a.yr <= b.yr) || (a.yl <= b.yl && b.yr <= a.yr); }
int main()
{
n = read();
for (int i = 1; i <= n; i++)
p[i].x = read(), p[i].y = read(), p[i].id = i, p[i].o = 0;
for (int i = 1 + n; i <= n + n; i++)
p[i].x = read(), p[i].y = read(), p[i].id = i - n, p[i].o = 1;
std::sort(p + 1, p + n * 2 + 1, [](Point a, Point b){ return a.y != b.y ? a.y < b.y : a.o < b.o; });
for (int i = 1; i <= n * 2; i++)
{
yy[i] = p[i].y;
if (p[i].o == 0) rec.insert(p[i]);
else
{
auto it = rec.lower_bound(p[i]);
if (it == rec.begin()) return printf("No\n"), 0;
--it, ans[it->id] = p[i].id;
sg[++m] = Segment(it->x, it->y, p[i].y, 1);
sg[++m] = Segment(p[i].x + 1, it->y, p[i].y, -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, r));
if (sg[i].v == 1 && BIT::query(l, r) > 0)
return printf("No\n"), 0;
if (sg[i].v == -1 && BIT::query(l, r) != 2)
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: 0
Wrong Answer
time: 0ms
memory: 9884kb
input:
3 0 0 2 -2 1 1 2 2 3 1 2 3
output:
No
result:
wrong answer expected YES, found NO