QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#549121#8179. 2D ParenthesesHuTaoWA 225ms23468kbC++142.5kb2024-09-06 09:39:312024-09-06 09:39:31

Judging History

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

  • [2024-09-06 09:39:31]
  • 评测
  • 测评结果:WA
  • 用时:225ms
  • 内存:23468kb
  • [2024-09-06 09:39:31]
  • 提交

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;
}

詳細信息

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'