Submission #1334152

#TimeUsernameProblemLanguageResultExecution timeMemory
1334152MrAndriaPort Facility (JOI17_port_facility)C++20
0 / 100
0 ms344 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],vis[1000005];
pair <int,int> a[1000005];
pair <int,int> d_r[4000005];
bool b1;
pair <int,int> query_r(int v,int tl,int tr,int l,int r){
    if(l>r){
        return make_pair(0,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 max(query_r(2*v,tl,tm,l,min(r,tm)),query_r(2*v+1,tm+1,tr,max(l,tm+1),r));
    }
}
void update_r(int v,int tl,int tr,int pos,pair <int,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]=max(d_r[2*v],d_r[2*v+1]);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    t=1;
    // cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=2*n;i++){
            update_r(1,1,2*n,i,make_pair(0,i));
        }
        for(int i=1;i<=n;i++){
            cin>>a[i].ff;
            cin>>a[i].ss;
            // cout<<a[i]<<" "<<b[i]<<" "<<i<<endl;
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            update_r(1,1,2*n,a[i].ff,make_pair(a[i].ss,i));
        }
        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_r(1,1,2*n,a[i].ff,make_pair(0,i));
                while(!q.empty()){
                    auto x=q.front();
                    q.pop();
                    while(true){
                        auto k=query_r(1,1,2*n,a[x].ff+1,a[x].ss-1);
                        // cout<<k.ff<<" "<<k.ss<<" r "<<x<<endl;
                        if(k.ff>a[x].ss){
                            q.push(k.ss);
                            vis[k.ss]=3-vis[x];
                            update_r(1,1,2*n,a[k.ss].ff,make_pair(0,k.ss));
                        }else{
                            break;
                        }
                    }

                }
            }
        }
        for(int i=1;i<=n;i++){
            c[a[i].ff]=i;
            c[a[i].ss]=-i;
        }
        stack <int> st[2];
        for(int i=1;i<=2*n;i++){
            // cout<<val[abs(c[i])]<<" "<<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();
            }
        }
        
        cout<<ans<<endl;
        

    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...