Submission #132169

#	Time	Username	Problem	Language	Result	Execution time	Memory
132169		IC_COLDSTOP	Port Facility (JOI17_port_facility)	C++17	0 / 100	121 ms	110080 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];
pii arr[MX];
set<int> vec[MX];

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

void join(int u, int v){
    if((u=parent(u))==(v=parent(v))) return;
    if(par[u]>par[v]) swap(u,v);
    for(auto w:vec[v]) vec[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){
        int a, b;
        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(b);
        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(MP((*vec[cur].begin()), cur));
            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);
        st.insert(MP((*vec[cur].begin()),cur));
    }
    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(MP((*vec[cur].begin()), cur));
        st.erase(st.begin());
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int32_t main()':
port_facility.cpp:34:13: warning: unused variable 'a' [-Wunused-variable]
         int a, b;
             ^
port_facility.cpp:34:16: warning: unused variable 'b' [-Wunused-variable]
         int a, b;
                ^

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