Submission #677582

#	Time	Username	Problem	Language	Result	Execution time	Memory
677582		FedShat	Port Facility (JOI17_port_facility)	C++17	100 / 100	3692 ms	391796 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

vector<pair<int, int>> lr;
vector<int> used;

struct SegTree {
    struct Node {
        int mx = -INF, imx = -1, mn = INF, imn = -1;

        Node() = default;
        Node(int v, int i) {
            mx = mn = v;
            imx = imn = i;
        }
    };

    Node pull(const Node &a, const Node &b) {
        Node ans;
        if (a.mx > b.mx) {
            ans.mx = a.mx;
            ans.imx = a.imx;
        } else {
            ans.mx = b.mx;
            ans.imx = b.imx;
        }
        if (a.mn < b.mn) {
            ans.mn = a.mn;
            ans.imn = a.imn;
        } else {
            ans.mn = b.mn;
            ans.imn = b.imn;
        }
        return ans;
    }

    vector<Node> tree;
    int n;

    SegTree() {}
    SegTree(int n) : n(n) {
        tree.resize(4 * n);
    }

    void update(int v, int l, int r, int i, int x) {
        if (l + 1 == r) {
            tree[v] = {x, l};
            return;
        }
        int m = (l + r) / 2;
        if (i < m) {
            update(2 * v + 1, l, m, i, x);
        } else {
            update(2 * v + 2, m, r, i, x);
        }
        tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
    }

    void update(int i, int x) {
        update(0, 0, n, i, x);
    }

    Node get(int v, int l, int r, int li, int ri) {
        if (li >= r || l >= ri) {
            return Node();
        }
        if (li <= l && r <= ri) {
            return tree[v];
        }
        int m = (l + r) / 2;
        return pull(get(2 * v + 1, l, m, li, ri), get(2 * v + 2, m, r, li, ri));
    }

    Node get(int li, int ri) {
        return get(0, 0, n, li, ri);
    }
};

SegTree st1, st2;
vector<pair<int, int>> v;

void dfs(int i, int c) {
    used[i] = c;
    auto [li, ri] = lr[i];
    st1.update(li, -INF);
    st2.update(ri, INF);
    while (1) {
        auto [mx, j, kek1, kek2] = st1.get(li, ri);
        if (mx < ri) {
            break;
        }
        assert(used[v[j].first] == -1);
        dfs(v[j].first, c ^ 1);
    }
    while (1) {
        auto [kek1, kek2, mn, j] = st2.get(li, ri);
        if (mn > li) {
            break;
        }
        assert(used[v[j].first] == -1);
        dfs(v[j].first, c ^ 1);
    }
    // for (int j = 0; j < (int) lr.size(); ++j) {
    //     if (i == j || used[j] != -1) {
    //         continue;
    //     }
    //     auto [li, ri] = lr[i];
    //     auto [lj, rj] = lr[j];
    //     if (li < lj && lj < ri && rj > ri) { // li lj ri rj
    //         dfs(j, c ^ 1);
    //     }
    //     if (li < rj && rj < ri && lj < li) { // lj li rj ri
    //         dfs(j, c ^ 1);
    //     }
    // }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n;
    cin >> n;
    lr.resize(n);
    v.resize(2 * n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        lr[i] = {a, b};
        v[a] = {i, 1};
        v[b] = {i, -1};
    }
    used.resize(n, -1);
    st1 = SegTree(2 * n);
    st2 = SegTree(2 * n);
    for (int i = 0; i < n; ++i) {
        auto [l, r] = lr[i];
        st1.update(l, r);
        st2.update(r, l);
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (used[i] == -1) {
            dfs(i, 0);
            ++cnt;
        }
    }
    vector<vector<int>> chel(2);
    bool ok = 1;
    for (int i = 0; i < 2 * n; ++i) {
        if (v[i].second == 1) {
            chel[used[v[i].first]].push_back(lr[v[i].first].second);
        } else {
            if (!chel[0].empty() && chel[0].back() == i) {
                chel[0].pop_back();
            } else if (!chel[1].empty() && chel[1].back() == i) {
                chel[1].pop_back();
            } else {
                ok = 0;
                break;
            }
        }
    }
    if (!ok) {
        cout << 0;
    } else {
        ll ans = 1;
        constexpr int mod = 1e9 + 7;
        for (int i = 0; i < cnt; ++i) {
            (ans *= 2) %= mod;
        }
        cout << ans;
    }
}

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