제출 #656208

#제출 시각아이디문제언어결과실행 시간메모리
656208ilia_rrPort Facility (JOI17_port_facility)C++17
0 / 100
2 ms4180 KiB
// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ // Written by Ilia Rahbar // #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math") // #pragma GCC target ("abm,bmi,bmi2,tbm,avx2") #include <bits/stdc++.h> using namespace std; #define int int64_t #define ai(x) array <int, x> #define F first #define S second const int MOD = 1e9 + 7, N = 1e5 + 100; ai(2) a[N]; int n, l[N * 2], vs[N], c, ans = 1, cv[N]; set <int> s; set <int> :: iterator itr; struct DSU { vector <int> v[N]; int t[N], d[N]; DSU(int x) { for (int i = 1; i <= x; i++) { v[i].push_back(i); t[i] = i; d[i] = 0; } } bool mr(int x, int y) { if (t[x] == t[y]) { if (abs(d[x] - d[y]) % 2 == 0) { cout << 0; exit(0); } return 0; } if (v[t[x]].size() < v[t[y]].size()) swap(x, y); for (auto i : v[t[y]]) { t[i] = t[x]; v[t[x]].push_back(i); d[i] += d[x] + 1; } return 1; } }; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1]; sort(a, a+n); for (int i = 0; i < n; i++) { l[a[i][0]] = i+1; l[a[i][1]] = i+1; } DSU d(n); for (int i = 1; i <= n * 2; i++) { if (vs[l[i]]) { s.erase(l[i]); itr = s.end(); while (s.size()) { itr--; if (*itr < l[i]) break; d.mr(l[i], *itr); if (itr == s.begin()) break; } } else { vs[l[i]] = 1; s.insert(l[i]); } } for (int i = 1; i <= n; i++) { if (!cv[d.t[i]]) { c++; cv[d.t[i]] = 1; } } for (int i = 0; i < c; i++) ans = (ans * 2) % MOD; 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...