Submission #671973

#	Time	Username	Problem	Language	Result	Execution time	Memory
671973		tengiz05	Port Facility (JOI17_port_facility)	C++17	100 / 100	2310 ms	223968 KiB

port_facility

#include <bits/stdc++.h>
 
using i64 = long long;
 
constexpr int P = 1E9 + 7;

constexpr int N = 2E6 + 5;

struct Info {
    int mn;
    int mx;
    Info(int x = N, int y = -1) : mn(x), mx(y) {}
};
Info operator+(const Info &a, const Info &b) {
    Info c;
    c.mn = std::min(a.mn, b.mn);
    c.mx = std::max(a.mx, b.mx);
    return c;
}

struct SegmentTree {
    int n;
    std::vector<Info> t;
    SegmentTree(int n) : n(n), t(4 * n) {}
    void modify(int p, int l, int r, int x, Info y) {
        if (l == r - 1) {
            t[p] = y;
        } else {
            int m = (l + r) / 2;
            if (x < m) {
                modify(2 * p, l, m, x, y);
            } else {
                modify(2 * p + 1, m, r, x, y);
            }
            t[p] = t[2 * p] + t[2 * p + 1];
        }
    }
    void modify(int x, int y) {
        modify(1, 0, n, x, Info(y, y));
    }
    void remove(int x) {
        modify(1, 0, n, x, Info());
    }
    Info query(int p, int l, int r, int x, int y) {
        if (r <= x || y <= l) {
            return Info();
        }
        if (x <= l && r <= y) {
            return t[p];
        }
        int m = (l + r) / 2;
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n;
    std::cin >> n;
    
    std::vector<int> a(n), b(n);
    std::vector<int> p(2 * n), id(2 * n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        p[a[i]] = b[i];
        p[b[i]] = a[i];
        id[a[i]] = id[b[i]] = i;
    }
    
    std::vector<bool> vis(n);
    
    std::vector<int> color(n);
    vis.assign(n, false);
    
    SegmentTree s(2 * n);
    
    for (int i = 0; i < 2 * n; i++) {
        s.modify(i, p[i]);
    }
    
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            c++;
            std::function<void(int)> dfs = [&](int u) {
                vis[u] = true;
                s.remove(a[u]);
                s.remove(b[u]);
                while (true) {
                    Info x = s.query(a[u], b[u]);
                    if (x.mn < a[u]) {
                        color[id[x.mn]] = color[u] ^ 1;
                        dfs(id[x.mn]);
                    } else if (x.mx > b[u]) {
                        color[id[x.mx]] = color[u] ^ 1;
                        dfs(id[x.mx]);
                    } else {
                        break;
                    }
                }
            };
            dfs(i);
        }
    }
    
    std::stack<int> st[2];
    for (int i = 0; i < 2 * n; i++) {
        if (p[i] > i) {
            st[color[id[i]]].push(id[i]);
        } else {
            if (st[color[id[i]]].top() != id[i]) {
                std::cout << "0\n";
                return 0;
            }
            st[color[id[i]]].pop();
        }
    }
    
    int ans = 1;
    for (int i = 0; i < c; i++) {
        ans = 2 * ans % P;
    }
    
    std::cout << ans << "\n";
    
    return 0;
}

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