Submission #1116141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116141		Blistering_Barnacles	Port Facility (JOI17_port_facility)	C++17	100 / 100	2731 ms	234704 KiB

port_facility

//Billions of bilious blue blistering barnacles in a thundering typhoon!
//Yesterday is history, tomorrow is a mystery, today is a gift of God, which is why we call it the present.
#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    auto mrg = [&](pair<pair<int, int>, pair<int, int>> u, pair<pair<int, int>, pair<int, int>> v) {
        return make_pair(max(u.first, v.first), min(u.second, v.second));
    };
    vector<vector<int>> adj(n + 1);
    vector<pair<pair<int, int>, pair<int, int>>> tree(8 * n + 1, {{INT_MIN, 0}, {INT_MAX, 0}});
    function<void(int, int, int, int, pair<int, int>)> update = [&](int s, int e, int node, int i, pair<int, int> val) {
        if (s > i || e < i) return;
        if (e == s) {
            tree[node].first = max(tree[node].first, val);
            tree[node].second = min(tree[node].second, val);
            return;
        }
        int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
        update(s, md, lx, i, val), update(md + 1, e, rx, i, val);
        tree[node] = mrg(tree[lx], tree[rx]);
    };
    function<pair<pair<int, int>, pair<int, int>>(int, int, int, int, int)> query = [&](int s, int e, int node, int l, int r) {
        if (s > r || e < l) return tree[0];
        if (l <= s && e <= r) return tree[node];
        int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
        return mrg(query(s, md, lx, l, r), query(md + 1, e, rx, l, r));
    };
    for (int i = 1; i <= n; i++) {
        auto [l, r] = a[i];
        update(1, 2 * n, 1, l, make_pair(r, i));
        update(1, 2 * n, 1, r, make_pair(l, i));
    }
    auto add = [&](int u, int v) {
        adj[u].push_back(v), adj[v].push_back(u);
    };
    for (int i = 1; i <= n; i++) {
        auto [l, r] = a[i];
        auto [mx, mn] = query(1, 2 * n, 1, l + 1, r - 1);
        if (mx.first > r) add(mx.second, i);
        if (mn.first < l) add(mn.second, i);
    }
    vector<int> col(n + 1);
    int ans = 1;
    auto dfs = [&](auto &&self, int v) -> void {
        for (int u: adj[v]) {
            if (col[u]) {
                if (col[u] == col[v]) ans = 0;
            } else {
                col[u] = 3 - col[v];
                self(self, u);
            }
        }
    };
    for (int i = 1; i <= n; i++) {
        if (!col[i]) {
            col[i] = 1;
            ans = ans * 2 % 1000000007;
            dfs(dfs, i);
        }
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

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