QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#549119#8179. 2D ParenthesesHuTaoWA 217ms23660kbC++142.5kb2024-09-06 09:36:122024-09-06 09:36:12

Judging History

你现在查看的是最新测评结果

  • [2024-09-06 09:36:12]
  • 评测
  • 测评结果:WA
  • 用时:217ms
  • 内存:23660kb
  • [2024-09-06 09:36:12]
  • 提交

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