제출 #671973

#제출 시각아이디문제언어결과실행 시간메모리
671973tengiz05Port Facility (JOI17_port_facility)C++17
100 / 100
2310 ms223968 KiB
#include <bits/stdc++.h> using i64 = long long; constexpr int P = 1E9 + 7; constexpr int N = 2E6 + 5; struct Info { int mn; int mx; Info(int x = N, int y = -1) : mn(x), mx(y) {} }; Info operator+(const Info &a, const Info &b) { Info c; c.mn = std::min(a.mn, b.mn); c.mx = std::max(a.mx, b.mx); return c; } struct SegmentTree { int n; std::vector<Info> t; SegmentTree(int n) : n(n), t(4 * n) {} void modify(int p, int l, int r, int x, Info y) { if (l == r - 1) { t[p] = y; } else { int m = (l + r) / 2; if (x < m) { modify(2 * p, l, m, x, y); } else { modify(2 * p + 1, m, r, x, y); } t[p] = t[2 * p] + t[2 * p + 1]; } } void modify(int x, int y) { modify(1, 0, n, x, Info(y, y)); } void remove(int x) { modify(1, 0, n, x, Info()); } Info query(int p, int l, int r, int x, int y) { if (r <= x || y <= l) { return Info(); } if (x <= l && r <= y) { return t[p]; } int m = (l + r) / 2; return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y); } Info query(int l, int r) { return query(1, 0, n, l, r); } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(NULL); int n; std::cin >> n; std::vector<int> a(n), b(n); std::vector<int> p(2 * n), id(2 * n); for (int i = 0; i < n; i++) { std::cin >> a[i] >> b[i]; a[i]--; b[i]--; p[a[i]] = b[i]; p[b[i]] = a[i]; id[a[i]] = id[b[i]] = i; } std::vector<bool> vis(n); std::vector<int> color(n); vis.assign(n, false); SegmentTree s(2 * n); for (int i = 0; i < 2 * n; i++) { s.modify(i, p[i]); } int c = 0; for (int i = 0; i < n; i++) { if (!vis[i]) { c++; std::function<void(int)> dfs = [&](int u) { vis[u] = true; s.remove(a[u]); s.remove(b[u]); while (true) { Info x = s.query(a[u], b[u]); if (x.mn < a[u]) { color[id[x.mn]] = color[u] ^ 1; dfs(id[x.mn]); } else if (x.mx > b[u]) { color[id[x.mx]] = color[u] ^ 1; dfs(id[x.mx]); } else { break; } } }; dfs(i); } } std::stack<int> st[2]; for (int i = 0; i < 2 * n; i++) { if (p[i] > i) { st[color[id[i]]].push(id[i]); } else { if (st[color[id[i]]].top() != id[i]) { std::cout << "0\n"; return 0; } st[color[id[i]]].pop(); } } int ans = 1; for (int i = 0; i < c; i++) { ans = 2 * ans % P; } std::cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...