QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423256#8179. 2D ParentheseslefyWA 307ms28156kbC++142.7kb2024-05-27 21:54:082024-05-27 21:54:09

Judging History

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

  • [2024-05-27 21:54:09]
  • 评测
  • 测评结果:WA
  • 用时:307ms
  • 内存:28156kb
  • [2024-05-27 21:54:08]
  • 提交

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 Lx[N<<1],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--;
        Lx[i]=a[i].x,Ly[i]=a[i].y,a[i].id=i;

    }
    sort(Lx+1,Lx+1+n*2),sort(Ly+1,Ly+1+n*2);
    int X=unique(Lx+1,Lx+1+n*2)-Lx-1;
    Y=unique(Ly+1,Ly+1+n*2)-Ly-1;
    for(int i=1;i<=n*2;i++){
        a[i].x=lower_bound(Lx+1,Lx+1+X,a[i].x)-Lx,a[i].y=lower_bound(Ly+1,Ly+1+Y,a[i].y)-Ly;
        // cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].id<<"\n";
    }
    sort(a+1,a+n*2+1,cmp);
    for(int i=1;i<=n*2;i++){
        
        // cout<<a[i].id<<"\n";
        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;
            }
            // 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";
                    }
                    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: 5ms
memory: 20240kb

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: 4ms
memory: 18096kb

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 307ms
memory: 28156kb

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:

*1 33120
2446  123389
2445  221948
1 33238
No

result:

wrong output format YES or NO expected, but *1 found