Submission #996689

#	Time	Username	Problem	Language	Result	Execution time	Memory
996689		peterandvoi	Port Facility (JOI17_port_facility)	C++17	100 / 100	4430 ms	253108 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

using ll = long long;

const int N = 1e6 + 5, MOD = 1e9 + 7, inf = 1e9;

int n;
int c[N], a[N], b[N];

struct Segtree {
    array<int, 2> s[8 * N];

    void upd(int i, array<int, 2> v) {
        int id = 1, l = 1, r = 2 * n;
        while (l ^ r) {
            int md = (l + r) / 2;
            id *= 2;
            if (i <= md) {
                r = md;
            } else {
                l = md + 1;
                id += 1;
            }
        }
        s[id] = v;
        while (id > 1) {
            id /= 2;
            s[id] = max(s[id * 2], s[id * 2 + 1]);
        }
    }

    array<int, 2> get(int id, int l, int r, int u, int v) {
        if (u <= l && r <= v) {
            return s[id];
        }
        int md = (l + r) / 2;
        if (u <= md && md < v) {
            return max(get(id * 2, l, md, u, v), get(id * 2 + 1, md + 1, r, u, v));
        }
        if (md < u) {
            return get(id * 2 + 1, md + 1, r, u, v);
        }
        return get(id * 2, l, md, u, v);
    }

    array<int, 2> get(int l, int r) {
        return get(1, 1, 2 * n, l, r);
    }
};

Segtree A, B;

void dfs(int u) {
    A.upd(a[u], {-inf, -1});
    B.upd(b[u], {-inf, -1});
    array<int, 2> v;
    while ((v = A.get(a[u], b[u]))[0] > b[u]) {
        c[v[1]] = c[u] ^ 1;
        dfs(v[1]);
    }
    while (-(v = B.get(a[u], b[u]))[0] < a[u]) {
        c[v[1]] = c[u] ^ 1;
        dfs(v[1]);
    }
}

void reset() {
    for (int i = 1; i <= 2 * n; ++i) {
        A.upd(i, {-inf, -1});
        B.upd(i, {-inf, -1});
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n;
    reset();
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        c[i] = -1;
        A.upd(a[i], {b[i], i});
        B.upd(b[i], {-a[i], i});
    }
    int res = 1;
    for (int i = 1; i <= n; ++i) {
        if (c[i] == -1) {
            c[i] = 0;
            dfs(i);
            res = ll(res) * 2 % MOD;
        }
    }
    reset();
    for (int i = 1; i <= n; ++i) {
        if (c[i] == 0) {
            A.upd(a[i], {b[i], i});
            B.upd(b[i], {-a[i], i});
            if (A.get(a[i], b[i])[0] > b[i] || -B.get(a[i], b[i])[0] < a[i]) {
                cout << 0;
                exit(0);
            }
        }
    }
    reset();
    for (int i = 1; i <= n; ++i) {
        if (c[i] == 1) {
            A.upd(a[i], {b[i], i});
            B.upd(b[i], {-a[i], i});
            if (A.get(a[i], b[i])[0] > b[i] || -B.get(a[i], b[i])[0] < a[i]) {
                cout << 0;
                exit(0);
            }
        }
    }
    cout << res;
}

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