Submission #1197488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197488		og_matveychick1	Port Facility (JOI17_port_facility)	C++20	100 / 100	3103 ms	599472 KiB

port_facility

#include "bits/stdc++.h"

using namespace std;

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

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

struct node {
    ll f, o;
    vector<ll> tl, tr;
};

ll n, l[N], r[N], c[N], p[N], idr[2 * N], idl[2 * N], ans = 1, rr[2 * N], rl[2 * N];
node t[4 * N];
queue<ll> q;

void build(ll v, ll l1, ll r1) {
    if (l1 + 1 == r1) {
        if (idr[l1] != -1) t[v].tl.push_back(r[idr[l1]]);
        if (idl[l1] != -1) t[v].tr.push_back(l[idl[l1]]);
        return;
    }
    ll m = (l1 + r1) / 2;
    build(v * 2, l1, m), build(v * 2 + 1, m, r1);
    t[v].tl.resize(t[v * 2].tl.size() + t[v * 2 + 1].tl.size());
    merge(t[v * 2].tl.begin(), t[v * 2].tl.end(), t[v * 2 + 1].tl.begin(), t[v * 2 + 1].tl.end(), t[v].tl.begin());
    t[v].tr.resize(t[v * 2].tr.size() + t[v * 2 + 1].tr.size());
    merge(t[v * 2].tr.begin(), t[v * 2].tr.end(), t[v * 2 + 1].tr.begin(), t[v * 2 + 1].tr.end(), t[v].tr.begin(),
          greater<ll>());
}

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

void add3(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) {
        while (t[v].tr.size() && t[v].tr.back() < L) {
            if (!c[rl[t[v].tr.back()]]) c[rl[t[v].tr.back()]] = x, q.push(rl[t[v].tr.back()]);
            t[v].tr.pop_back();
        }
        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 add4(ll v, ll l1, ll r1, ll L, ll R) {
    if (l1 > L || r1 <= L) return;
    t[v].f = max(t[v].f, R);
    if (l1 + 1 == r1) return;
    ll m = (l1 + r1) / 2;
    add4(v * 2, l1, m, L, R);
    add4(v * 2 + 1, m, r1, L, R);
}

void add4(ll L, ll R) {
    add4(1, 0, 2 * N, L, R);
}

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) {
        while (t[v].tl.size() && t[v].tl.back() > R) {
            if (!c[rr[t[v].tl.back()]]) c[rr[t[v].tl.back()]] = x, q.push(rr[t[v].tl.back()]);
            t[v].tl.pop_back();
        }
        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) {
    if (l1 >= R || r1 <= L) return;
    if (l1 >= L && r1 <= R) {
        t[v].o = min(t[v].o, R);
        return;
    }
    ll m = (l1 + r1) / 2;
    add2(v * 2, l1, m, L, R);
    add2(v * 2 + 1, m, r1, L, R);
}

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

bool check(ll v, ll l1, ll r1) {
    if (t[v].o < t[v].f) {
        return 0;
    }
    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);
    n = 1e6;
    cin >> n;
    memset(idl, -1, sizeof idl);
    memset(idr, -1, sizeof idr);
    for (ll i = 0; i < n; i++) {
        l[i] = i + 1, r[i] = 2 * n - i;
        cin >> l[i] >> r[i];
        idr[l[i]] = i;
        idl[r[i]] = i;
        rr[r[i]] = i;
        rl[l[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);
//            add4(l[i], r[i], c[i]);
            _--;
        } else {
            ll i = p[_];
            if (c[i]) continue;
            ans = (ans * 2) % mod;
            c[i] = 1;
            add1(l[i], r[i], 3 - c[i], i);
            add3(l[i], r[i], 3 - c[i], i);
//            add4(l[i], r[i], c[i]);
        }
    }
//    for (ll i = 0; i < 4 * N; i++) t[i].s.clear();
    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;
    for (ll x = 1; x <= 2; x++) {
        for (ll i = 0; i < 4 * N; i++) t[i].o = 1e9, t[i].f = -1;
        for (ll i = 0; i < n; i++) {
            if (c[i] == x) add4(l[i], r[i]), add2(l[i], r[i]);
        }
        ans *= check();
    }
    cout << ans;
}

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