Submission #1197435

#TimeUsernameProblemLanguageResultExecution timeMemory
1197435og_matveychick1Port Facility (JOI17_port_facility)C++20
0 / 100
133 ms136036 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> v1, v2, og; }; ll n, l[N], r[N], c[N], p[N], id[2 * N], ans = 1, pr[N]; node t[4 * N]; void build(ll v, ll l1, ll r1) { if (l1 + 1 == r1) { if (id[l1] != -1) t[v].v1 = 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); t[v].v1.resize(t[v * 2].v1.size() + t[v * 2 + 1].v1.size()); merge(t[v * 2].v1.begin(), t[v * 2].v1.end(), t[v * 2 + 1].v1.begin(), t[v * 2 + 1].v1.end(), t[v].v1.begin()); t[v].v2 = t[v].v1; } 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; } 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].v1.size() && t[v].v1.back().first > R) { if (!c[t[v].v1.back().second]) c[t[v].v1.back().second] = x; t[v].v1.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, 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; for (ll i = 0; i < 2 * n; i++) id[i] = -1; 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; _++) { ll i = p[_]; 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...