Submission #459496

#TimeUsernameProblemLanguageResultExecution timeMemory
459496S920105123Port Facility (JOI17_port_facility)C++14
100 / 100
1242 ms190904 KiB
#include <bits/stdc++.h> #define LL long long #define PII pair<int, int> const LL MOD = (LL) 1e9 + 7; const int MAXN = 2000005; using namespace std; struct Interval { int l, r; }; struct DSU { int pa[MAXN]; void init(int n) { for (int i = 0; i <= n; i++) { pa[i] = i; } } int find(int x) { return x == pa[x] ? x : pa[x] = find(pa[x]); } int merge(int x, int y) { assert(x <= y); x = find(x); y = find(y); assert(x <= y); if (x == y) return 0; pa[x] = y; return 1; } } U_nxt, U_jmp; int n, col[MAXN], id[MAXN]; vector<int> G[MAXN]; Interval I[MAXN]; void add_edge(int u, int v) { G[u].push_back(v); G[v].push_back(u); } int dfs(int v, int c) { int ok = 1; col[v] = c; for (int to : G[v]) { if (col[to] == -1) { ok &= dfs(to, c ^ 1); } else { ok &= (col[to] != col[v]); } } return ok; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; U_jmp.init(2 * n + 1); U_nxt.init(2 * n + 1); for (int i = 1; i <= n; i++) { cin >> I[i].l >> I[i].r; } sort(I + 1, I + 1 + n, [&] (Interval a, Interval b) { return a.l < b.l; }); for (int i = 1; i <= n; i++) { U_jmp.merge(I[i].l, I[i].l + 1); U_nxt.merge(I[i].l, I[i].l + 1); id[I[i].l] = id[I[i].r] = i; } for (int i = n; i >= 1; i--) { U_nxt.merge(I[i].r, I[i].r + 1); int pre = -1, cur = U_nxt.find(I[i].l); while (cur < I[i].r) { add_edge(id[cur], i); if (pre != -1) { U_jmp.merge(pre, cur); } pre = cur; cur = U_jmp.find(cur); cur = U_nxt.find(cur + 1); } } int cc = 0; fill(col + 1, col + 1 + n, -1); for (int i = 1; i <= n; i++) { if (col[i] == -1) { if (!dfs(i, 0)) { cout << "0\n"; return 0; } cc++; } } LL ans = 1; for (int i = 0; i < cc; i++) { ans = ans * 2 % MOD; } 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...