Submission #231490

#	Time	Username	Problem	Language	Result	Execution time	Memory
231490		2fat2code	Port Facility (JOI17_port_facility)	C++17	100 / 100	1900 ms	210640 KiB

port_facility

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int mod=1e9+7;

const int nmax=1000005;

int n,ans=1,par[nmax],siz[nmax];
vector<int>color[2];
pair<int,int>a[nmax];
vector<int>nod[nmax];
bitset<nmax>viz;

int fin(int x){
    if(x!=par[x]){
        par[x]=fin(par[x]);
    }
    return par[x];
}

int join(int a,int b){
    nod[a].push_back(b);
    nod[b].push_back(a);
    a=fin(a);
    b=fin(b);
    if(a!=b){
        if(siz[a]<siz[b]) swap(a,b);
        siz[a]+=siz[b];
        par[b]=a;
    }
}

void DFS(int s,int dist){
    viz[s]=1;
    color[dist%2].push_back(s);
    for(auto it:nod[s]){
        if(!viz[it]) DFS(it,dist+1);
    }
}

bool check(int c){
    sort(all(color[c]));
    vector<pair<int,int>>activ;
    for(auto it:color[c]){
        while(activ.size() && a[it].fr>activ.back().sc) activ.pop_back();
        if(activ.empty()) activ.push_back({a[it].fr,a[it].sc});
        else{
            if(a[it].fr<activ.back().sc && a[it].sc>activ.back().sc) rcc(0);
            else activ.push_back({a[it].fr,a[it].sc});
        }
    }
    return true;
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n;
    for(int i=1;i<=n;i++) par[i]=i,siz[i]=1;
    for(int i=1;i<=n;i++) cin >> a[i].fr >> a[i].sc;
    sort(a+1,a+n+1);
    set<pair<int,int>>st;
    for(int i=1;i<=n;i++){
        if(i>=2) st.insert({a[i-1].sc,i-1});
        auto it_L=st.lower_bound({a[i].fr,0});
        if(it_L==st.end()) continue;
        if(it_L->first>a[i].sc) continue;
        auto it_R=st.lower_bound({a[i].sc,0});
        it_R--;
        auto last=it_R;
        it_R++;
        while(it_L!=it_R){
            join(it_L->second,i);
            if(fin(it_L->second)==fin(last->second)) break;
            it_L++;
        }
    }
    for(int i=1;i<=n;i++){
        if(par[i]==i){
            ans=(ans*2)%mod;
            DFS(i,0);
            check(0);
            check(1);
            color[0].clear();
            color[1].clear();
        }
    }
    cout << ans << '\n';
}

Compilation message (stderr)

port_facility.cpp: In function 'long long int join(long long int, long long int)':
port_facility.cpp:42:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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