제출 #996689

#제출 시각아이디문제언어결과실행 시간메모리
996689peterandvoiPort Facility (JOI17_port_facility)C++17
100 / 100
4430 ms253108 KiB
#include <bits/stdc++.h> using namespace std; #ifdef ngu #include "debug.h" #else #define debug(...) 42 #endif using ll = long long; const int N = 1e6 + 5, MOD = 1e9 + 7, inf = 1e9; int n; int c[N], a[N], b[N]; struct Segtree { array<int, 2> s[8 * N]; void upd(int i, array<int, 2> v) { int id = 1, l = 1, r = 2 * n; while (l ^ r) { int md = (l + r) / 2; id *= 2; if (i <= md) { r = md; } else { l = md + 1; id += 1; } } s[id] = v; while (id > 1) { id /= 2; s[id] = max(s[id * 2], s[id * 2 + 1]); } } array<int, 2> get(int id, int l, int r, int u, int v) { if (u <= l && r <= v) { return s[id]; } int md = (l + r) / 2; if (u <= md && md < v) { return max(get(id * 2, l, md, u, v), get(id * 2 + 1, md + 1, r, u, v)); } if (md < u) { return get(id * 2 + 1, md + 1, r, u, v); } return get(id * 2, l, md, u, v); } array<int, 2> get(int l, int r) { return get(1, 1, 2 * n, l, r); } }; Segtree A, B; void dfs(int u) { A.upd(a[u], {-inf, -1}); B.upd(b[u], {-inf, -1}); array<int, 2> v; while ((v = A.get(a[u], b[u]))[0] > b[u]) { c[v[1]] = c[u] ^ 1; dfs(v[1]); } while (-(v = B.get(a[u], b[u]))[0] < a[u]) { c[v[1]] = c[u] ^ 1; dfs(v[1]); } } void reset() { for (int i = 1; i <= 2 * n; ++i) { A.upd(i, {-inf, -1}); B.upd(i, {-inf, -1}); } } int main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef ngu freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); #endif cin >> n; reset(); for (int i = 1; i <= n; ++i) { cin >> a[i] >> b[i]; c[i] = -1; A.upd(a[i], {b[i], i}); B.upd(b[i], {-a[i], i}); } int res = 1; for (int i = 1; i <= n; ++i) { if (c[i] == -1) { c[i] = 0; dfs(i); res = ll(res) * 2 % MOD; } } reset(); for (int i = 1; i <= n; ++i) { if (c[i] == 0) { A.upd(a[i], {b[i], i}); B.upd(b[i], {-a[i], i}); if (A.get(a[i], b[i])[0] > b[i] || -B.get(a[i], b[i])[0] < a[i]) { cout << 0; exit(0); } } } reset(); for (int i = 1; i <= n; ++i) { if (c[i] == 1) { A.upd(a[i], {b[i], i}); B.upd(b[i], {-a[i], i}); if (A.get(a[i], b[i])[0] > b[i] || -B.get(a[i], b[i])[0] < a[i]) { cout << 0; exit(0); } } } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...