Submission #1155968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155968		anmattroi	Port Facility (JOI17_port_facility)	C++17	10 / 100	1 ms	584 KiB

port_facility

#include <bits/stdc++.h>
#define maxn 1000005
#define fi first
#define se second

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

constexpr int mod = 1000000007;

int n;
map<int, int> rd;
set<int> ww, ll;
ii a[maxn];

void ins(const int &a, const int &b) {
    auto it = rd.lower_bound(a);
    if (it != rd.end() && it->se <= b) return;
    it = rd.insert(it, {a, b});
    it->se = b;
    while (it != rd.begin() && prev(it)->se >= b) rd.erase(prev(it));
}

int nho[2*maxn];
int par[maxn], slt;

int find_set(int v) {
    return par[v] < 0 ? v : par[v] = find_set(par[v]);
}

void union_set(int u, int v) {
    u = find_set(u); v = find_set(v);
    if (u == v) return;
    if (par[u] < par[v]) swap(u, v);
    --slt;
    par[v] += par[u];
    par[u] = v;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    slt = n;
    for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++) {
        par[i] = -1;
        nho[a[i].fi] = nho[a[i].se] = i;
    }

    for (int i = 1; i <= n; i++) {
        auto START = ww.lower_bound(a[i].fi), END = ww.lower_bound(a[i].se);
        vector<int> vals;
        for (auto it = START; it != END; it++) {
            union_set(i, nho[*it]);
            vals.emplace_back(*it);
        }
        for (int x : vals) ww.erase(x);
        auto it = rd.lower_bound(a[i].fi);
        if (it != rd.end() && it->se < a[i].se) {cout << 0; exit(0);}
        ll.insert(a[i].se);
        ww.insert(a[i].se);
        auto ti = ll.lower_bound(a[i].se);
        if (ti != ll.begin()) {
            --ti;
            ins(*ti, a[i].se);
            if (*ti > a[i].fi) union_set(nho[*ti], i);
        }

    }
    int ans = 1;
    while (slt--) ans = ans * 2 % mod;
    cout << ans;
}

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