Submission #957107

#	Time	Username	Problem	Language	Result	Execution time	Memory
957107		efishel	Port Facility (JOI17_port_facility)	C++17	0 / 100	6 ms	25692 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 1E6+16, MOD = 1E9+7, IDEM = ll(1E18)+16;
vll adj[MAXN];
bool col[MAXN];
bool vis[MAXN];

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    struct Node {
        ll minN, maxN;

        Node (ll valmin, ll valmax): minN(valmin), maxN(valmax) {}
        Node (): minN(IDEM), maxN(-IDEM) {} // INF

        Node operator+ (const Node &o) {
            Node ans;
            ans.minN = min(minN, o.minN);
            ans.maxN = max(maxN, o.maxN);
            return ans;
        }
    };
    vector <Node> tree;
    ll n;
    
    SegTree (ll n): tree(2*n, Node()), n(n) {}

    void update (ll at, Node node) { update(at, node, 0, n-1, 0); }
    void update (ll at, Node node, ll l, ll r, ll id) {
        if (at < l || r < at) return;
        if (at <= l && r <= at) { tree[id] = node; return; }
        update(at, node, l, mid, id+1);
        update(at, node, mid+1, r, id+off);
        tree[id] = tree[id+1] + tree[id+off];
    }

    void idemize (ll at) { update(at, Node()); } // idempotentize

    Node query (ll ql, ll qr) { return query(ql, qr, 0, n-1, 0); }
    Node query (ll ql, ll qr, ll l, ll r, ll id) {
        if (qr < l || r < ql) return Node(); // IDEM node
        if (ql <= l && r <= qr) return tree[id];
        return query(ql, qr, l, mid, id+1) + query(ql, qr, mid+1, r, id+off);
    }
};

bool dfs_paint (ll u, ll par) {
    if (vis[u]) return false;
    vis[u] = true;
    for (ll v : adj[u]) {
        if (v == par) continue;
        col[v] = !col[u];
        dfs_paint(v, u);
    }
    return true;
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n;
    cin >> n;
    vll who(2*n);
    vector <pair <ll, ll> > ve(n);
    for (auto &[l, r] : ve) { cin >> l >> r; l--; r--; }
    for (ll i = 0; i < n; i++) { auto [l, r] = ve[i]; who[l] = i; who[r] = i; }
    SegTree st(2*n);
    for (ll i = 0; i < n; i++) {
        auto [l, r] = ve[i];
        st.update(l, SegTree::Node(IDEM, r));
        st.update(r, SegTree::Node(l, -IDEM));
    }
    // we draw edges between intersecting segments, and then delete them
    for (ll i = 0; i < n; i++) {
        auto [l, r] = ve[i];
        {SegTree::Node th;
        while (th = st.query(l, r), th.maxN > r) {
            adj[i].push_back(who[th.maxN]);
            adj[who[th.maxN]].push_back(i);
            auto [aul, aur] = ve[who[th.maxN]];
            st.idemize(aul);
            st.idemize(aur);
        }}
        {SegTree::Node th;
        while (th = st.query(l, r), th.minN < l) {
            adj[i].push_back(who[th.minN]);
            adj[who[th.minN]].push_back(i);
            auto [aul, aur] = ve[who[th.minN]];
            st.idemize(aul);
            st.idemize(aur);
        }}
    }
    // we get a forest of trees, not all edges are drawn in this process, but all interlocked nodes are connected
    ll ans = 1;
    // we paint them accordingly (a tree is always bipartite)
    for (ll u = 0; u < n; u++) if (dfs_paint(u, u)) ans = 2*ans % MOD;
    // we check the extra edges that we didn't draw by straight up simulating it
    stack <ll> stA, stB;
    for (ll i = 0; i < 2*n; i++) {
        ll u = who[i];
        if (col[u] == 0) if (stA.size() && stA.top() == u) stA.pop(); else stA.push(u);
        if (col[u] == 1) if (stB.size() && stB.top() == u) stB.pop(); else stB.push(u);
    }
    if (stA.size() == 0 && stB.size() == 0) cout << ans << '\n';
    else cout << "0\n";
    // we check whether the process concluded successfully or not
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:104:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  104 |         if (col[u] == 0) if (stA.size() && stA.top() == u) stA.pop(); else stA.push(u);
      |            ^
port_facility.cpp:105:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  105 |         if (col[u] == 1) if (stB.size() && stB.top() == u) stB.pop(); else stB.push(u);
      |            ^

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