QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423107 | #8179. 2D Parentheses | complexor | WA | 197ms | 27412kb | C++23 | 2.8kb | 2024-05-27 21:08:20 | 2024-05-27 21:08:21 |
Judging History
answer
#include <bits/stdc++.h>
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 = 400005;
struct Point
{
int x, y, id, o;
friend bool operator<(Point a, Point b){ return a.x != b.x ? a.x < b.x : a.y < b.y; }
} 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
{
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++)
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;
if (n <= 2) return printf("NO"), 0;
std::sort(p + 1, p + n * 2 + 1, [](Point a, Point b){ return a.y != b.y ? a.y < b.y : a.x > b.x; });
for (int i = 1; i <= n * 2; i++)
{
// printf("%d %d %d %d\n", p[i].x, p[i].y, p[i].id, p[i].o);
// if (i == 4) for (Point t : rec) printf("%d %d %d %d\n", t.x, t.y, t.id, t.o);
yy[i] = p[i].y;
if (p[i].o == 0) rec.insert(p[i]);
else
{
auto it = rec.lower_bound(Point(p[i].x - 1, 1e9 + 1, 0, 0));
if (it == rec.begin()) return printf("No\n"), 0;
// printf("!%d\n", it->id);
--it, ans[it->id] = p[i].id;
// printf("%d: %d\n", i, it->id);
sg[++m] = Segment(it->x, it->y, p[i].y, 1);
sg[++m] = Segment(p[i].x, 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 + 1, r - 1));
if (sg[i].v == 1 && l < r && BIT::query(l + 1, r - 1) > 0) ;
// return printf("No"), 0;
if (sg[i].v == -1 && l < r && 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: 9944kb
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: 7800kb
input:
2 1 0 0 1 2 3 3 2
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 1ms
memory: 7940kb
input:
1 1 1 0 0
output:
NO
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 197ms
memory: 27412kb
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 163202 52754 29196 93486 2981 198023 157367 48765 123135 18491 80650 112519 196489 109656 173973 5551 113259 136548 133688 182366 59175 165032 163355 93530 5843 31857 130090 155862 76890 97333 133685 85853 167272 4006 27179 1988 107334 29064 65560 70618 115785 151179 183975 13637 114...
result:
wrong answer 3rd words differ - expected: '59327', found: '163202'