Submission #1185925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185925		lambd47	Port Facility (JOI17_port_facility)	C++20	In queue	0 ms	0 KiB

port_facility

#include <bits/stdc++.h>

#define int long long
using namespace std;


std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int MOD=1e9+7;





void solve() {
    int n;cin>>n;
    vector<int> l(n),r(n);
    vector<int> evs(2*n);
    vector<int> sai(2*n,-1);
    vector<int> invr(2*n);
    for(int i=0;i<n;i++){
        cin>>l[i]>>r[i];
        l[i]--;
        r[i]--;
        invr[r[i]]=i;
    }
    sort(r.begin(),r.end(),[&](int a, int b){
            return l[invr[a]]<l[invr[b]];
    });
    sort(l.begin(),l.end());
    vector<vector<int>> adj(n);
    for(int i=0;i<n;i++){
        sai[r[i]]=i;
    }
    for(int i=0;i<n;i++){
        evs[l[i]]=i+1;
        evs[r[i]]=-i-1;
    }

    stack<int> st;
    vector<bool> tirei(n,0);

    for(int j=0,i=0;i<2*n;i++){
        if(sai[i]!=-1){
            if(tirei[sai[i]])continue;
            int bst=-1;
            int d=-1;
            while(!st.empty() && st.top()!=sai[i]){
                adj[sai[i]].push_back(st.top());
                adj[st.top()].push_back(sai[i]);
                if(r[st.top()]>d){
                    bst=st.top();
                    d=r[bst];
                }
                tirei[st.top()]=1;
                st.pop();
            }

            if(!st.empty() && st.top()==sai[i])st.pop();
            if(bst!=-1){
                st.push(bst);
                tirei[bst]=0;
            }
        }
        if(l[j]==i){
            st.push(j);
            j++;
        }
    }
    vector<bool> vis(n,0);
    vector<int> cor(n,0);
    auto dfs=[&](auto&& self,int node)->void{
        vis[node]=1;
        for(auto a: adj[node]){
            if(vis[a])continue;
            cor[a]=cor[node]^1;
            self(self,a);
        }
    };
    int c=0;

    for(int i=0;i<n;i++){
        if(!vis[i]){
           dfs(dfs,i);
           c++;
        }
    }

    int resp=1;
    int pat=2;
    for(int i=0;i<25;i++){
        if(c&(1<<i)){
            resp*=pat;
            resp%=MOD;
        }
        pat*=pat;
        pat%=MOD;
    }

    stack<int> s[2];

    for(int i=0;i<2*n;i++){
        if(evs[i]>0){
            int a=--evs[i];
            s[cor[a]].push(a);
        }
        if(evs[i]<0){
            int a=++evs[i];
            a=-a;
            if(s[cor[a]].top()!=a){
                cout<<0;return;
            }
            s[cor[a]].pop();
        }
    }



    cout<<resp<<endl;
    return;



    for(int i=0;i<n;i++){
        for(auto a: adj[i]){
            cout<<a<<" ";
        }
        cout<<endl;
    }







}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}