제출 #655944

#제출 시각아이디문제언어결과실행 시간메모리
655944mosaevPort Facility (JOI17_port_facility)C++17
78 / 100
6065 ms643100 KiB
#pragma GCC optimize("-Ofast") #include <bits/stdc++.h> #include <set> #include <map> using namespace std; #define ll long long #define N (ll)(1e6+5) #define NP (4194304ll) #define M ((ll)1e9+7) #define fi first #define se second ll ans; ll n, ft[N], t[N * 2], grp[N], p[N], cnt; vector<ll> v[N]; map<ll, ll> seg[NP], st; inline void get(ll l, ll r) { l += 2097151ll, r += 2097151ll; st.clear(); while (l <= r) { if (l & 1) { for (auto x : seg[l]) st[x.first] |= x.second; l++; } if (!(r & 1)) { for (auto x : seg[r]) st[x.first] |= x.second; r--; } l >>= 1, r >>= 1; } } inline void upd(ll x, ll a, ll b, ll c) { x += 2097151ll; while (x > 0) { seg[x].erase(a); seg[x][b] |= c; x >>= 1; } } inline void merge(ll a, ll b, ll c) { c &= grp[a]; a = p[a]; if (v[a].size() < v[b].size()) swap(a, b); for (auto x : v[b]) { p[x] = a; v[a].push_back(x); if (c) grp[x] ^= 3; upd(ft[x], b, a, grp[x]); }v[b].clear(); cnt--; } int main() { #define int ll ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); ll a, b; cin >> n; for (int i = 1; i <= n; i++) cin >> a >> b, ft[i] = b, t[a] = t[b] = i, p[i] = i, v[i].push_back(i), grp[i] = 1; cnt = n; for (int i = 1; i <= 2 * n; i++) { if (ft[t[i]] == i) continue; a = t[i]; get(i, ft[a]); for (auto x : st) { if (x.second == 3) return cout << 0 << '\n', 0; merge(a, x.first, x.second); } upd(ft[a], 0, p[a], grp[a]); } ans = 1; for (int i = 1; i <= cnt; i++) ans <<= 1, ans %= M; 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...