Submission #996799

#	Time	Username	Problem	Language	Result	Execution time	Memory
996799		peterandvoi	Port Facility (JOI17_port_facility)	C++17	100 / 100	907 ms	64704 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

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

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

int n;
int lab[N], c[N];
array<int, 2> p[N], s[8 * N];

int get(int u) {
    if (lab[u] < 0) {
        return u;
    }
    int p = get(lab[u]);
    c[u] ^= c[lab[u]];
    return lab[u] = p;
}

bool unite(int u, int v, int x) {
    int a = get(u);
    int b = get(v);
    x ^= c[u] ^ c[v];
    if (a == b) {
        return !x;
    }
    if (lab[a] > lab[b]) {
        swap(a, b);
    }
    lab[b] = a;
    c[b] = x;
    return true;
}

void upd(array<int, 2> &x) {
    if (x[1] == 0 || x[1] == 3) {
        return;
    }
    int p = get(x[0]);
    x[1] = (x[1] - 1) ^ c[x[0]];
    x[1]++;
    x[0] = p;
}

array<int, 2> operator + (array<int, 2> &u, array<int, 2> &v) {
    upd(u);
    upd(v);
    if (u[0] == 0 || v[0] == 0) {
        return max(u, v);
    }
    if (u[0] == v[0] && u[1] && v[1]) {
        return {u[0], u[1] | v[1]};
    }
    return {MOD, 0};
}

void upd(int i, int x) {
    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] = {x, 1};
    if (x == 2) {
        upd(s[id]);
    }
    while (id > 1) {
        id /= 2;
        s[id] = s[id * 2] + s[id * 2 + 1];
    }
}

void unite(array<int, 2> &x, int i) {
    if (x[1] == 3 || !unite(x[0], i, 2 - x[1])) {
        cout << 0;
        exit(0);
    }
    upd(x);
}

void mrg(int u, int v, int i, int id = 1, int l = 1, int r = 2 * n) {
    if (s[id][0] == 0) {
        return;
    }
    if (u <= l && r <= v && s[id][1]) {
        unite(s[id], i);
        return;
    }
    int md = (l + r) / 2;
    if (u <= md) {
        mrg(u, v, i, id * 2, l, md);
    }
    if (md < v) {
        mrg(u, v, i, id * 2 + 1, md + 1, r);
    }
    s[id] = s[id * 2] + s[id * 2 + 1];
}

auto main() -> int {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i][0] >> p[i][1];
    }
    fill(lab + 1, lab + n + 1, -1);
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; ++i) {
        auto [l, r] = p[i];
        mrg(l, r, i);
        upd(r, i);
    }
    int res = 1;
    for (int i = 1; i <= n; ++i) {
        if (lab[i] < 0) {
            res = 1LL * res * 2 % MOD;
        }
    }
    cout << res;
}

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