Submission #1312266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312266		VMaksimoski008	Port Facility (JOI17_port_facility)	C++20	100 / 100	1777 ms	231324 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int mod = 1e9 + 7;
const int N = 1e6 + 5;

struct segment_tree {
    int n;
    vector<pii> tree;

    segment_tree(int _n) : n(_n), tree(3*n, { 1e9, 0 }) {}

    void update(int p, pii v) {
        for(tree[p+=n]=v; p>1; p>>=1)
            tree[p>>1] = min(tree[p], tree[p^1]);
    }

    pii query(int l, int r) {
        pii ans = { 1e9, 0 };
        for(l+=n,r+=n+1; l<r; l>>=1, r>>=1) {
            if(l&1) ans = min(ans, tree[l++]);
            if(r&1) ans = min(ans, tree[--r]);
        }
        return ans;
    }
};

ll ans = 1;
int col[N];
vector<int> g[N];

void dfs(int u, int c) {
    col[u] = c;

    for(int v : g[u]) {
        if(!col[v]) dfs(v, 3 - c);
        else if(col[v] == col[u]) ans = 0;
    }
}

signed main() {
    int n; cin >> n;
    segment_tree sgtL(2*n), sgtR(2*n);
    vector<int> l(n+1), r(n+1), a(2*n+1);
    for(int i=1; i<=n; i++) {
        cin >> l[i] >> r[i];
        a[l[i]] = a[r[i]] = i;
        sgtL.update(r[i], { l[i], i });
        sgtR.update(l[i], { -r[i], i });
    }

    for(int i=1; i<=n; i++) {
        int pl = sgtL.query(l[i], r[i]).second;
        int pr = sgtR.query(l[i], r[i]).second;

        if(pl && l[pl] < l[i]) {
            g[pl].push_back(i);
            g[i].push_back(pl);
        }

        if(pr && r[pr] > r[i]) {
            g[pr].push_back(i);
            g[i].push_back(pr);
        }
    }

    for(int i=1; i<=n; i++) {
        if(col[i]) continue;
        ans = (ans * 2) % mod;
        dfs(i, 1);
    }
    cout << ans << '\n';
}

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