Submission #45580

#	Time	Username	Problem	Language	Result	Execution time	Memory
45580		qoo2p5	Port Facility (JOI17_port_facility)	C++17	100 / 100	3103 ms	379652 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = (int) 1e6 + 123;
const ll MOD = (ll) 1e9 + 7;

int n;
int a[N], b[N];
vector<int> adj[N], g[N];
int col[N];
int p[N];
int cnt[N];

void dfs(int v, int cc = 1) {
    col[v] = cc;
    for (int u : g[v]) {
        if (!col[u]) {
            dfs(u, 3 - cc);
        }
        if (col[u] != 3 - cc) {
            cout << "0\n";
            exit(0);
        }
    }
}

int get(int v) {
    return (p[v] == v ? v : (p[v] = get(p[v])));
}

void unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u != v) {
        p[u] = v;
        cnt[v] += cnt[u];
    }
}

bool closed[N];
pair<int, bool> what[2 * N];

int L[N], R[N];

void run() {
    rep(i, 0, N) p[i] = i, cnt[i] = 1;
    
    cin >> n;
    rep(i, 0, n) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        what[a[i]] = {i, 0};
        what[b[i]] = {i, 1};
    }
    
    {
        set<int> q;
        rep(i, 0, 2 * n) {
            if (what[i].second) {
                continue;
            }
            int v = what[i].first;
            auto it = q.insert(b[v]).first;
            if (it != q.begin()) {
                --it;
                R[v] = *it;
            } else {
                R[v] = -1;
            }
        }
    }
    
    {
        set<int> q;
        per(i, 2 * n - 1, 0) {
            if (!what[i].second) {
                continue;
            }
            int v = what[i].first;
            auto it = q.insert(a[v]).first;
            ++it;
            if (it != q.end()) {
                L[v] = *it;
            } else {
                L[v] = INF;
            }
        }
    }
    
    rep(i, 0, n) {
        if (L[i] < R[i]) {
            cout << "0\n";
            return;
        }
    }
    
    vector<int> st, tmp;
    rep(i, 0, 2 * n) {
        int v = what[i].first;
        
        if (what[i].second) {
            while (1) {
                while (cnt[st.back()] == 0) {
                    st.pop_back();
                }
                int t = st.back();
                if (t == get(v)) {
                    break;
                }
                st.pop_back();
                if (cnt[t]) {
                    tmp.pb(t);
                }
            }
            
            if (sz(tmp)) {
                rep(i, 1, sz(tmp)) {
                    unite(tmp[0], tmp[i]);
                }
                int u = get(tmp[0]);
                adj[v].pb(u);
                adj[u].pb(v);
                st.pb(u);
                tmp.clear();
            }
            
            cnt[get(v)]--;
        } else {
            st.pb(v);
        }
    }
    
    rep(v, 0, n) {
        for (int u : adj[v]) {
            g[get(v)].pb(get(u));
        }
    }
    
    ll ans = 1;
    
    rep(i, 0, n) {
        if (get(i) == i && !col[i]) {
            dfs(i);
            ans = (ans * 2) % MOD;
        }
    }
    
    cout << ans << "\n";
}

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