QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549127 | #8179. 2D Parentheses | HuTao | WA | 228ms | 23520kb | C++14 | 2.5kb | 2024-09-06 09:49:54 | 2024-09-06 09:49:54 |
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 = n * 2; i >= 1; 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: 12120kb
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: 11992kb
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: 5884kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 228ms
memory: 23520kb
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 143937 85506 159482 29196 103293 188581 65913 156903 48765 41010 76203 137133 196363 193426 109982 116023 34701 44848 99488 40423 194556 59175 165032 44597 44935 5843 122285 62483 155862 76890 97333 46778 56089 167272 163892 142018 158865 116989 191396 183211 91317 199137 56352 10550 16401...
result:
wrong answer 1st words differ - expected: '21701', found: '82079'