QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549121 | #8179. 2D Parentheses | HuTao | WA | 225ms | 23468kb | C++14 | 2.5kb | 2024-09-06 09:39:31 | 2024-09-06 09:39:31 |
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 && n <= 2) 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: 2ms
memory: 12088kb
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: 0ms
memory: 12024kb
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: 5636kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 225ms
memory: 23468kb
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 82079 174709 172848 159482 29196 103293 188581 65913 61229 48765 41010 76203 137133 196363 193426 101630 116023 34701 44848 47047 40423 194556 59175 165032 112955 44935 5843 110260 62483 185365 76890 97333 145165 56089 167272 163892 142018 158865 116989 191396 183211 10874 115785 56352 10550 164...
result:
wrong answer 1st words differ - expected: '21701', found: '82079'