Submission #592413

#	Time	Username	Problem	Language	Result	Execution time	Memory
592413		AA_Surely	Port Facility (JOI17_port_facility)	C++17	100 / 100	2259 ms	129064 KiB

port_facility

#include <bits/stdc++.h>

#define FOR(i, x, y)    for(int i = x; i < y; i++) 
#define F0R(i, y)       FOR(i, 0, y)
#define ROF(i, x, y)    for(int i = y - 1; i >= x; i--)
#define R0F(i, y)       ROF(i, 0, y)

#define WTF             cout << "WTF" << endl

#define ALL(x)          x.begin(), x.end()
#define RALL(x)         x.rbegin(), x.rend();

#define IOS             ios_base::sync_with_stdio(0); cin.tie(0)
#define F               first
#define S               second
#define pb              push_back

using namespace std;

typedef pair<int, int>  PII;

const int N = 2e6 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;

#define lc now << 1
#define rc now << 1 | 1

int n, f[N];
int exist[N];
bool vis[N], comp[N];
PII ns[N];
PII tree[2][N << 2];
queue<int> keep;
stack<int> dr;

void change(int id, int place, PII x, int now = 1, int ls = 0, int rs = (n << 1) - 1) {
    if (ls == rs) {
        tree[id][now] = x;
        return;
    }

    int mid = (ls + rs) >> 1;
    if (place <= mid) change(id, place, x, lc, ls, mid);
    else change(id, place, x, rc, mid + 1, rs);
    
    if (!id) tree[0][now] = max(tree[0][lc], tree[0][rc]);
    else tree[1][now] = min(tree[1][lc], tree[1][rc]);

    return;
}

void init() {
    cin >> n;
    
    F0R(i, (n << 3)) tree[1][i] = {INF, INF};

    F0R(i, n) {
        cin >> ns[i].F >> ns[i].S;
        ns[i].F--; ns[i].S--;
    }

    F0R(i, n) {
        change(0, ns[i].F, {ns[i].S, i});
        change(1, ns[i].S, {ns[i].F, i});
    }

    return;
}

void getEdge(int lq, int rq, int now = 1, int ls = 0, int rs = (n << 1) - 1) {
    if (rq < lq || rq < ls || rs < lq) return;
    if (lq <= ls && rs <= rq) {
        while(1) {
            PII on = tree[0][now];
            if (on.F <= rq) break;
            dr.push(on.S);
            change(0, ns[on.S].F, {0, 0});
            change(1, ns[on.S].S, {INF, INF});
        }

        while(1) {
            PII on = tree[1][now];
            if (on.F >= lq) break;
            //cout << on.F << ' ' << on.S << endl;
            dr.push(on.S);
            change(0, ns[on.S].F, {0, 0});
            change(1, ns[on.S].S, {INF, INF});
        }

        return;
    }

    int mid = (ls + rs) >> 1;
    getEdge(lq, rq, lc, ls, mid);
    getEdge(lq, rq, rc, mid + 1, rs);

    return;
}

void bfs(int now) {
    //cout << "bfs from " << now << endl;
    vis[now] = 1;
    comp[now] = 0;

    change(0, ns[now].F, {0, 0});
    change(1, ns[now].S, {INF, INF});

    keep.push(now);

    while(!keep.empty()) {
        int on = keep.front();
        keep.pop();
        //cout << "get Edge for " << on << endl;
        getEdge(ns[on].F, ns[on].S);

        //cout << "Edges = ";
        while(!dr.empty()) {
            int x = dr.top(); dr.pop();
            //cout << x << ' ';

            comp[x] = 1 ^ comp[on];
            vis[x] = 1;
            keep.push(x);
        }
        //cout << endl;
    }

    return;
}

bool check() {
    memset(f, 0, sizeof f);
    F0R(i, n) if (!comp[i]) f[ ns[i].F ] = (i + 1), f[ ns[i].S ] = -(i + 1);

    stack<int> st;
    F0R(i, (n << 1)) if (f[i]) {
        if (f[i] > 0) st.push(f[i]);
        else {
            if (st.empty() || st.top() != -f[i]) return 0;
            st.pop();
        }
    }

    memset(f, 0, sizeof f);
    F0R(i, n) if (comp[i]) f[ ns[i].F ] = (i + 1), f[ ns[i].S ] = -(i + 1);

    while(!st.empty()) st.pop();
    F0R(i, (n << 1)) if (f[i]) {
        if (f[i] > 0) st.push(f[i]);
        else {
            if (st.empty() || st.top() != -f[i]) return 0;
            st.pop();
        }
    }
    return 1;
}

int main() {
    IOS;

    init();

    int ans = 1;
    F0R(i, n) if (!vis[i]) {
        bfs(i);
        ans = (ans << 1) % MOD;
    }

    cout << (check() ? ans : 0);
}

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