Submission #1197449

#TimeUsernameProblemLanguageResultExecution timeMemory
1197449og_matveychick1Port Facility (JOI17_port_facility)C++20
78 / 100
615 ms177464 KiB
#include "bits/stdc++.h"

using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

const ll N = 1 << 17, mod = 1e9 + 7;

struct node {
    vector<pll> v2, og;
    set<pll> s;
};

ll n, l[N], r[N], c[N], p[N], id[2 * N], ans = 1, pr[N];
node t[4 * N];
queue<ll> q;

void build(ll v, ll l1, ll r1) {
    if (l1 + 1 == r1) {
        if (id[l1] != -1) {
            t[v].s.insert({r[id[l1]], id[l1]});
            t[v].v2 = {{r[id[l1]], id[l1]}};
        }
        return;
    }
    ll m = (l1 + r1) / 2;
    build(v * 2, l1, m), build(v * 2 + 1, m, r1);
    for (auto x: t[v * 2].s) t[v].s.insert(x);
    for (auto x: t[v * 2 + 1].s) t[v].s.insert(x);
    t[v].v2.resize(t[v * 2].v2.size() + t[v * 2 + 1].v2.size());
    merge(t[v * 2].v2.begin(), t[v * 2].v2.end(), t[v * 2 + 1].v2.begin(), t[v * 2 + 1].v2.end(), t[v].v2.begin());
}

void build() {
    build(1, 0, 2 * N);
}


ll find_set(ll v) {
    return (pr[v] == v ? v : pr[v] = find_set(pr[v]));
}

void union_sets(ll u, ll v) {
    u = find_set(u), v = find_set(v);
    if (u == v) return;
    pr[v] = u;
}

ll getc(ll v, ll l1, ll r1, ll L, ll R) {
    if (l1 >= R || r1 <= L) return 0;
    if (l1 >= L && r1 <= R) {
        if (t[v].v2.size() && c[t[v].v2.back().second]) return 3 - c[t[v].v2.back().second];
        return 0;
    }
    ll m = (l1 + r1) / 2;
    return max(getc(v * 2, l1, m, L, R), getc(v * 2 + 1, m, r1, L, R));
}

ll getc(ll l1, ll r1) {
    return getc(1, 0, 2 * N, l1, r1);
}

void add3(ll v, ll l1, ll r1, ll L, ll R, ll x, ll i) {
    if (l1 >= L || r1 <= 0) return;
    if (l1 >= 0 && r1 <= L) {
        if (t[v].v2.size() && t[v].v2.back().first > R) union_sets(t[v].v2.back().second, i);
        auto it = t[v].s.lower_bound({L, 0});
        while (it != t[v].s.end() && it->first < R) {
            union_sets((*it).second, i);
            if (!c[(*it).second]) c[(*it).second] = x, q.push((*it).second);
            t[v].s.erase(it);
            it = t[v].s.lower_bound({L, 0});
        }
        return;
    }
    ll m = (l1 + r1) / 2;
    add3(v * 2, l1, m, L, R, x, i);
    add3(v * 2 + 1, m, r1, L, R, x, i);
}

void add3(ll l1, ll r1, ll x, ll i) {
    add3(1, 0, 2 * N, l1, r1, x, i);
}

void add1(ll v, ll l1, ll r1, ll L, ll R, ll x, ll i) {
    if (l1 >= R || r1 <= L) return;
    if (l1 >= L && r1 <= R) {
        if (t[v].v2.size() && t[v].v2.back().first > R) union_sets(t[v].v2.back().second, i);
        while (t[v].s.size() && (*--t[v].s.end()).first > R) {
            union_sets((*--t[v].s.end()).second, i);
            if (!c[(*--t[v].s.end()).second]) c[(*--t[v].s.end()).second] = x, q.push((*--t[v].s.end()).second);
            t[v].s.erase(--t[v].s.end());
        }
        return;
    }
    ll m = (l1 + r1) / 2;
    add1(v * 2, l1, m, L, R, x, i);
    add1(v * 2 + 1, m, r1, L, R, x, i);
}

void add1(ll l1, ll r1, ll x, ll i) {
    add1(1, 0, 2 * N, l1, r1, x, i);
}

void add2(ll v, ll l1, ll r1, ll L, ll R, ll x) {
    if (l1 >= R || r1 <= L) return;
    if (l1 >= L && r1 <= R) {
        t[v].og.push_back({R + 1, x});
        return;
    }
    ll m = (l1 + r1) / 2;
    add2(v * 2, l1, m, L, R, x);
    add2(v * 2 + 1, m, r1, L, R, x);
}

void add2(ll l1, ll r1, ll x) {
    add2(1, 0, 2 * N, l1, r1, x);
}

bool check(ll v, ll l1, ll r1) {
    bool f1 = 0, f2 = 0;
    ll it = 0;
    for (auto [ps, x]: t[v].og) {
        while (it < t[v].v2.size() && t[v].v2[it].first < ps) {
            if (f1 && c[t[v].v2[it].second] == 2) return 0;
            if (f2 && c[t[v].v2[it].second] == 1) return 0;
            it++;
        }
        (x == 1 ? f1 : f2) = 1;
        if (it != t[v].v2.size() && f1 && f2) return 0;
    }
    while (it < t[v].v2.size()) {
        if (f1 && c[t[v].v2[it].second] == 2) return 0;
        if (f2 && c[t[v].v2[it].second] == 1) return 0;
        it++;
    }
    if (l1 + 1 == r1) return 1;
    ll m = (l1 + r1) / 2;
    return check(v * 2, l1, m) & check(v * 2 + 1, m, r1);
}

bool check() {
    return check(1, 0, 2 * N);
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    memset(id, -1, sizeof id);
    for (ll i = 0; i < n; i++) cin >> l[i] >> r[i], id[l[i]] = i, pr[i] = i;
    build();
    iota(p, p + n, 0);
    sort(p, p + n, [&](ll x, ll y) { return l[x] < l[y]; });
    for (ll _ = 0; _ < n; _++) {
        if (q.size()) {
            ll i = q.front();
            q.pop();
            add1(l[i], r[i], 3 - c[i], i);
            add3(l[i], r[i], 3 - c[i], i);
            _--;
        } else {
            ll i = p[_];
            if (c[i]) continue;
            ans = (ans * 2) % mod;
            if (!c[i]) c[i] = getc(l[i], r[i]);
            if (!c[i]) c[i] = 1;
            add1(l[i], r[i], 3 - c[i], i);
        }
    }
    sort(p, p + n, [&](ll x, ll y) { return r[x] < r[y]; });
    for (ll _ = 0; _ < n; _++) {
        ll i = p[_];
        add2(l[i], r[i], 3 - c[i]);
    }
//    for (ll i = 0; i < n; i++) ans = (ans * (1 + (find_set(i) == i))) % mod;
    ans *= check();
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...