제출 #1334162

#제출 시각아이디문제언어결과실행 시간메모리
1334162MrAndriaPort Facility (JOI17_port_facility)C++20
100 / 100
2623 ms56940 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
//#define int long long
int l,r,n,t,m,mid,ans,sum,sum1,sum2,sum0,k,mod=1e9+7,c[2000005],a[1000005],b[1000005],vis[1000005];
int d_l[8000005],d_r[8000005];
vector <int> v,v1;
map <int,int> mp;
string s,s1;
bool b1;
int mx(int x,int y){
    if(b[x]>=b[y]){
        return x;
    }
    return y;
}
int mi(int x,int y){
    if(a[x]<=a[y]){
        return x;
    }
    return y;
}
int query_r(int v,int tl,int tr,int l,int r){
    if(l>r){
        return 0;
    }
    // cout<<v<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
    if(tl==l and tr==r){
        return d_r[v];
    }else{
        int tm=(tl+tr)/2;
        return mx(query_r(2*v,tl,tm,l,min(r,tm)),query_r(2*v+1,tm+1,tr,max(l,tm+1),r));
    }
}
int query_l(int v,int tl,int tr,int l,int r){
    if(l>r){
        return n+1;
    }

    if(tl==l and tr==r){
        return d_l[v];
    }else{
        int tm=(tl+tr)/2;
        return mi(query_l(2*v,tl,tm,l,min(r,tm)),query_l(2*v+1,tm+1,tr,max(l,tm+1),r));
    }
}
void update_l(int v,int tl,int tr,int pos,int val){
    if(tl==pos and tr==pos){
        d_l[v]=val;
    }else{
        int tm=(tl+tr)/2;
        if(pos<=tm){
            update_l(2*v,tl,tm,pos,val);
        }else{
            update_l(2*v+1,tm+1,tr,pos,val);
        }
        d_l[v]=mi(d_l[2*v],d_l[2*v+1]);
    }
}
void update_r(int v,int tl,int tr,int pos,int val){
    if(tl==pos and tr==pos){
        // cout<<v<<" "<<tr<<" "<<val.ff<<" "<<val.ss<<endl;
        d_r[v]=val;
        // cout<<d_r[v].ff<<" "<<d_r[v].ss<<endl;
    }else{
        int tm=(tl+tr)/2;
        if(pos<=tm){
            update_r(2*v,tl,tm,pos,val);
        }else{
            update_r(2*v+1,tm+1,tr,pos,val);
        }
        d_r[v]=mx(d_r[2*v],d_r[2*v+1]);
    }
}
void build(int v,int tl,int tr){
    if(tl==tr){
        d_l[v]=n+1;
        d_r[v]=0;
    }else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        d_l[v]=n+1;
        d_r[v]=0;
    }
}
int main(){
    t=1;
    // cin>>t;
    while(t--){
        scanf("%d",&n);
        build(1,1,2*n);
        a[0]=0;
        b[0]=0;
        b[n+1]=INT_MAX;
        a[n+1]=INT_MAX;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i],&b[i]);
            update_l(1,1,2*n,b[i],i);
            // l -> a[i];
            update_r(1,1,2*n,a[i],i);
            // r -> b[i];
            // cout<<a[i]<<" "<<b[i]<<" "<<i<<endl;
        }
        ans=1;
        for(int i=1;i<=n;i++){
            if(vis[i]==0){
                ans*=2;
                ans%=mod;
                queue <int> q;
                q.push(i);
                vis[i]=1;
                update_l(1,1,2*n,b[i],n+1);
                update_r(1,1,2*n,a[i],0);
                while(!q.empty()){
                    auto x=q.front();
                    q.pop();
                    while(true){
                        auto k=query_l(1,1,2*n,a[x]+1,b[x]-1);
                        // cout<<k.ff<<" "<<k.ss<<" l "<<x<<endl;
                        // if(k==0){
                        //     cout<<"YES1 "<<i<<" "<<x<<endl;
                        //     return 0;
                        // }
                        if(a[k]<a[x]){
                            q.push(k);
                            vis[k]=3-vis[x];
                            update_l(1,1,2*n,b[k],n+1);
                            update_r(1,1,2*n,a[k],0);
                        }else{
                            break;
                        }
                    }
                    // cout<<"HERE "<<i<<" "<<x<<endl;
                    // if(i==2){
                    //     return 0;
                    // }
                    while(true){
                        auto k=query_r(1,1,2*n,a[x]+1,b[x]-1);
                        // cout<<k.ff<<" "<<k.ss<<" r "<<x<<endl;
                        if(k>=n+1){
                            cout<<"YES"<<endl;
                            return 0;
                        }
                        if(b[k]>b[x]){
                            q.push(k);
                            vis[k]=3-vis[x];
                            update_l(1,1,2*n,b[k],n+1);
                            update_r(1,1,2*n,a[k],0);
                        }else{
                            break;
                        }
                    }

                }
            }
        }
        for(int i=1;i<=n;i++){
            c[a[i]]=i;
            c[b[i]]=-i;
        }
        stack <int> st[2];
        for(int i=1;i<=2*n;i++){
            // cout<<vis[abs(c[i])]-1<<" "<<i<<endl;
            if(c[i]>0){
                st[vis[c[i]]-1].push(c[i]);
            }else{
                if(st[vis[-c[i]]-1].top()!=abs(c[i])){
                    cout<<0<<endl;
                    return 0;
                }
                st[vis[-c[i]]-1].pop();
            }
        }
        
        printf("%d",ans);
        

    }
}

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In function 'int main()':
port_facility.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
port_facility.cpp:100:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |             scanf("%d%d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...