Submission #1197476

#TimeUsernameProblemLanguageResultExecution timeMemory
1197476og_matveychick1Port Facility (JOI17_port_facility)C++20
78 / 100
1868 ms1114112 KiB
#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; set<ll> s; }; ll n, l[N], r[N], c[N], p[N], id[2 * N], ans = 1, rr[2 * 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]]); } 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); } 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 >= L || r1 <= 0) return; if (l1 >= 0 && r1 <= L) { auto it = t[v].s.lower_bound(L); while (it != t[v].s.end() && *it < R) { if (!c[rr[*it]]) c[rr[*it]] = x, q.push(rr[*it]); t[v].s.erase(it); it = t[v].s.lower_bound(L); } 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].s.size() && (*--t[v].s.end()) > R) { if (!c[rr[(*--t[v].s.end())]]) c[rr[(*--t[v].s.end())]] = x, q.push(rr[(*--t[v].s.end())]); 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) { 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(id, -1, sizeof id); for (ll i = 0; i < n; i++) { l[i] = 1, r[i] = 2 * n; cin >> l[i] >> r[i]; id[l[i]] = i, rr[r[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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...