QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549119 | #8179. 2D Parentheses | HuTao | WA | 217ms | 23660kb | C++14 | 2.5kb | 2024-09-06 09:36:12 | 2024-09-06 09:36:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n, m, k;
struct Point
{
int x, y, c, id;
inline bool operator <(const Point &w) const
{
return x == w.x ? y > w.y : x > w.x;
}
}p[N];
set<pair<int, int> > s;
int res[N];
struct Segment
{
int x, l, r;
bool operator <(const Segment &w) const
{
return x < w.x;
}
}sg[N];
struct Query
{
int x, y, d;
bool operator <(const Query &w) const
{
return x < w.x;
}
}q[N];
int xx[N], ss;
int c[N];
long long ans;
inline void Add(int i, int d)
{
for(; i <= ss; i += i & -i) c[i] += d;
}
inline int Sum(int i)
{
int s = 0;
for(; i; i &= i - 1) s += c[i];
return s;
}
int main()
{
scanf("%d", &n);
for(int i = 0 + 1; i <= n * 1; i ++ ) scanf("%d%d", &p[i].x, &p[i].y), p[i].c = 0, p[i].id = i;
for(int i = n + 1; i <= n * 2; i ++ ) scanf("%d%d", &p[i].x, &p[i].y), p[i].c = 1, p[i].id = i;
sort(p + 1, p + n * 2 + 1);
for(int i = 1; i <= n * 2; i ++ )
if(p[i].c == 1)
{
// printf("*%d %d\n", p[i].x, p[i].y);
s.insert({p[i].y, i});
}
else
{
// printf("#%d %d\n", p[i].x, p[i].y);
set<pair<int, int> >::iterator it = s.lower_bound({p[i].y, 0});
if(it == s.end())
{
puts("No");
return 0;
}
int j = it->second;
res[p[i].id] = p[j].id - n;
sg[ ++ m] = {p[j].x, p[i].y - 1, p[j].y};
q[ ++ k] = {p[i].x, p[j].y, -1};
q[ ++ k] = {p[j].x - 1, p[j].y, 1};
xx[ ++ ss] = p[i].y, xx[ ++ ss] = p[j].y;
s.erase(it);
}
sort(sg + 1, sg + m + 1);
sort(q + 1, q + k + 1);
sort(xx + 1, xx + ss + 1);
ss = unique(xx + 1, xx + ss + 1) - xx - 1;
for(int i = 1, j = 1; i <= k; i ++ )
{
while(j <= m && sg[j].x <= q[i].x)
{
sg[j].l = lower_bound(xx + 1, xx + ss + 1, sg[j].l) - xx;
sg[j].r = lower_bound(xx + 1, xx + ss + 1, sg[j].r) - xx;
Add(sg[j].l, 1), Add(sg[j].r, -1);
j ++ ;
}
q[i].y = lower_bound(xx + 1, xx + ss + 1, q[i].y) - xx;
ans += q[i].d * Sum(q[i].y);
}
if(ans) puts("No");
else
{
puts("Yes");
for(int i = 1; i <= n; i ++ ) printf("%d\n", res[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12124kb
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: 9944kb
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: 5688kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 217ms
memory: 23660kb
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