QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423290#8179. 2D ParentheseslefyWA 241ms41444kbC++142.1kb2024-05-27 22:06:132024-05-27 22:06:14

Judging History

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

  • [2024-05-27 22:06:14]
  • 评测
  • 测评结果:WA
  • 用时:241ms
  • 内存:41444kb
  • [2024-05-27 22:06:13]
  • 提交

answer

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=4e5+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(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){
                    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 28392kb

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: 3ms
memory: 28284kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 3ms
memory: 28368kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 241ms
memory: 41444kb

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