Submission #132185

#	Time	Username	Problem	Language	Result	Execution time	Memory
132185		IC_COLDSTOP	Port Facility (JOI17_port_facility)	C++17	100 / 100	2948 ms	522352 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
ofstream fout ("out.txt");
#define ll long long
//#define int ll
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define pii pair<int,int>
#define REP(i,a,b) for(int i=a; i<b; i++)

const int MX=2e6+3, mod=1e9+7;

int n, cnt[MX], ans=1, par[MX], cl[MX];
pii arr[MX];
set<pii> vec[MX], veccl[2][MX];

int parent(int u){ return par[u]<0 ? u : par[u]=parent(par[u]); }

void join(int u, int v){
    int a=cl[u], b=cl[v];
    if((parent(u))==(parent(v))){
        //cout<<u<<" "<<v<<" "<<a<<" "<<b<<endl;
        if(a==b){
            cout<<0<<endl;
            exit(0);
        }
        return;
    }
    u=parent(u), v=parent(v);
    if(par[u]>par[v]) swap(u,v);
    for(auto w:vec[v]){
        vec[u].insert(w);
        if(a==b) cl[w.S]^=1;
        if(cl[w.S]) veccl[1][u].insert(w);
        else veccl[0][u].insert(w);
    }
    par[u]+=par[v];
    par[v]=u;
}

int32_t main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(par, -1,sizeof par);
    cin>>n;
    REP(i,0,n) cin>>arr[i].F>>arr[i].S;
    sort(arr, arr+n);
    set<pii> st;
    REP(i,0,n){
        //cout<<i<<endl;
        int a=arr[i].F, b=arr[i].S;
        vec[i].insert(MP(b,i));
        veccl[0][i].insert(MP(b,i));
        while(st.size() && (*st.begin()).F<a){
            auto u=(*st.begin());
            int cur=parent(u.S);
            vec[cur].erase(vec[cur].begin());
            if(!vec[cur].size()){
                ans=ans*2%mod;
                //cout<<cur<<" "<<par[cur]<<endl;
            }
            else st.insert((*vec[cur].begin()));
            st.erase(st.begin());
        }
        //cout<<i<<endl;
        while(st.size() && (*st.begin()).F<b){
            auto u=(*st.begin());
            join(u.S, i);
            st.erase(u);
        }
        int cur=parent(i), l=cl[(*vec[cur].begin()).S];
        st.insert((*vec[cur].begin()));
        auto u=veccl[l^1][cur].lower_bound(MP(a,0));
        if(u!=veccl[l^1][cur].end()) st.insert((*u));
        /*for(auto u:vec[cur]){
            if(u==(*vec[cur].begin())) continue;
            if(cl[u.S]!=l){
                st.insert(u);
                break;
            }
        }*/
    }
    while(st.size()){
        auto u=(*st.begin());
        int cur=parent(u.S);
        vec[cur].erase(vec[cur].begin());
        if(!vec[cur].size()){
            ans=ans*2%mod;
            //cout<<cur<<" "<<par[cur]<<endl;
        }
        else st.insert((*vec[cur].begin()));
        st.erase(st.begin());
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22