Submission #655961

#TimeUsernameProblemLanguageResultExecution timeMemory
655961KahouPort Facility (JOI17_port_facility)C++14
10 / 100
16 ms572 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int M = 1e9 + 7; const int N = 1e6 + 50; int n, L[N], R[N], par[N], sz[N], cnt; set<pii> sl, sr; int getroot(int u) { if (u == par[u]) return u; return par[u] = getroot(par[u]); } void uniset(int u, int v) { u = getroot(u), v = getroot(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); par[v] = u; sz[u] += sz[v]; cnt--; } void solve() { cin >> n; cnt = n; for (int i = 1; i <= n; i++) { cin >> L[i] >> R[i]; sl.insert({L[i], i}); sr.insert({R[i], i}); par[i] = i; sz[i] = 1; } bool flg = 1; while (sr.size()) { int u = sr.begin()->S; sr.erase(sr.begin()); sl.erase({L[u], u}); int prv = 1e9; auto it = sl.lower_bound({L[u], 0}); auto ed = sl.lower_bound({R[u], 0}); for (; it != ed; it++) { int v = it->S; if (R[v] > prv) { flg = 0; break; } prv = R[v]; uniset(u, v); } if (!flg) break; } if (!flg) return cout << 0 << endl, void(); int ans = 1; for (int i = 1; i <= cnt; i++) { ans <<= 1; if (ans >= M) ans -= M; } cout << ans << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); 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...