Submission #1178568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178568		Double_Slash	Port Facility (JOI17_port_facility)	C++20	100 / 100	700 ms	137252 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;
using pint = pair<int, int>;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    int x[n << 1], seen[n + 1]{}, other[n + 1];
    for (int i = 1; i <= n; ++i) {
        int l, r;
        cin >> l >> r;
        x[--l] = x[--r] = i;
    }
    vector<int> adj[n + 1];
    vector<pint> v;
    for (int i = 0; i < (n << 1); ++i) {
        if (seen[x[i]]++) {
            pint agg{-1, 0};
            for (; other[x[i]] < other[v.back().first]; v.pop_back()) {
                adj[x[i]].emplace_back(v.back().first);
                adj[v.back().first].emplace_back(x[i]);
                agg.second += v.back().second;
                agg.first = v.back().first;
            }
            if (not --v.back().second) v.pop_back();
            if (~agg.first) v.push_back(agg);
        } else {
            v.emplace_back(x[i], 1);
            other[x[i]] = i;
        }
    }
    int c[n + 1]{};
    function<void(int)> dfs = [&] (int i) {
        for (int j: adj[i]) {
            if (c[j]) continue;
            c[j] = 3 - c[i];
            dfs(j);
        }
    };
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (c[i]) continue;
        c[i] = 1;
        dfs(i);
        ans = (ans << 1) % MOD;
    }
    stack<int> st[3];
    for (int xi: x) {
        if (seen[xi]++ == 2) st[c[xi]].emplace(xi);
        else if (st[c[xi]].top() != xi) {
            cout << "0\n";
            return 0;
        } else st[c[xi]].pop();
    }
    cout << ans << endl;
}

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