QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423281#8179. 2D ParentheseslefyWA 310ms26724kbC++142.5kb2024-05-27 22:04:112024-05-27 22:04:12

Judging History

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

  • [2024-05-27 22:04:12]
  • 评测
  • 测评结果:WA
  • 用时:310ms
  • 内存:26724kb
  • [2024-05-27 22:04:11]
  • 提交

answer

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=2e5+10;
struct node{
    int x,y,id;
}a[N<<1];
int cmp(node x,node y){
    if(x.x!=y.x)return x.x<y.x;
    return x.y<y.y;
}
int Ly[N<<1];
vector<int>hav[N<<1];
int t[N<<1],Y;
void add(int x,int v){
    for(;x<=Y;x+=x&-x)t[x]+=v;
}
int q(int x){
    if(!x)return 0;
    int ans=0;
    for(;x;x-=x&-x)ans+=t[x];
    return ans;
}
int q(int l,int r){
    if(l>r)return 0;
    return q(r)-q(l-1);
}
int get(int l,int r,int x){
    if(!q(1,x))return -1;
    while(l<r){
        int mid=l+r>>1;
        if(q(mid+1,r))l=mid+1;
        else r=mid;
    }
    return l;
}
int ans[N<<1];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n*2;++i){
        scanf("%d%d",&a[i].x,&a[i].y);a[i].x<<=1,a[i].y<<=1;if(i>n)a[i].x--,a[i].y--;
        Ly[i]=a[i].y,a[i].id=i;

    }
    sort(Ly+1,Ly+1+n*2);
    Y=unique(Ly+1,Ly+1+n*2)-Ly-1;
    for(int i=1;i<=n*2;i++)a[i].y=lower_bound(Ly+1,Ly+1+Y,a[i].y)-Ly;
    sort(a+1,a+n*2+1,cmp);
    for(int i=1;i<=n*2;i++){
        if(a[i].id<=n){
            hav[a[i].y].push_back(i);
            add(a[i].y,1);
        }else{
            int pos=get(1,Y,a[i].y);
            if(pos==-1){
                printf("No\n");return 0;
            }
            // if(q(pos+1,a[i].y))cout<<"cnm\n";
            // cout<<a[i].id<<" "<<pos<<"\n";
            int x=hav[pos].back();hav[pos].pop_back();
            // cout<<x<<"\n";
            ans[a[i].id]=x;add(pos,-1);
            ans[a[x].id]=i;
        }
        // cout<<i<<"*\n";
    }
    // if(n>=100)cout<<"*";
    multiset<int>st;
    for(int i=1;i<=2*n;i++){
        
        int x=a[i].y,y=a[ans[a[i].id]].y;
        if(n>=100&&(y==123389||x==123398)){
            // cout<<a[i].x<<" "<<a[i].y<<"\n";
            // cout<<a[ans[a[i].id]].x<<" "<<" "<<a[ans[a[i].id]].y<<"\n";




        }
        if(a[i].id>n)st.erase(st.find(x)),st.erase(st.find(y));
        else{
            auto it=st.upper_bound(x);
            if(it!=st.end()){
                if(*(it)<y){
                    if(n>=100){
                        // cout<<a[ans[a[i].id]].x<<" "<<" "<<a[ans[a[i].id]].y<<"\n";
                        // cout<<a[i].x<<" "<<a[i].y<<"\n";
                    }
                    if(n<100){printf("No\n");return 0;}
                }
            }
            st.insert(x),st.insert(y);
        }
    }
    printf("Yes\n");
    for(int i=1;i<=n;i++)printf("%d\n",a[ans[i]].id-n);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 16120kb

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: 18088kb

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: 18092kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 310ms
memory: 26724kb

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
125911
24064
131376
24130
40012
70025
126129
65913
39416
14669
110521
49808
163083
111711
44237
109982
173973
92477
141927
161003
3329
98374
146130
110179
153382
78378
63476
163368
161659
22532
180060
22555
105965
192669
77221
4006
142534
85606
157007
60723
139898
143593
53129
6656
13162
91316
4...

result:

wrong answer 1st words differ - expected: '21701', found: '125911'