Submission #752924

#TimeUsernameProblemLanguageResultExecution timeMemory
752924bgnbvnbvPort Facility (JOI17_port_facility)C++14
22 / 100
6017 ms58028 KiB
#include <bits/stdc++.h> #define ll long long #define pll pair<ll, ll> #define pii pair<ll, pll> #define pb push_back #define fi first #define se second using namespace std; const int N = 2e6+5; const ll mod = 1e9 + 7; const int base = 40; ll n, m, k, t, a[N], b[N], tong, dp[N], lab[N], ans; char c; vector<ll> adj[N], kq; pll p[N]; ll pw(ll k, ll n) { ll total = 1; for(; n; n >>= 1) { if(n & 1)total = total * k % mod; k = k * k % mod; } return total; } ll findp(ll u) { return lab[u] < 0 ? u : lab[u] = findp(lab[u]); } void hop(ll u, ll v) { if(lab[u] > lab[v])swap(u, v); lab[u] += lab[v]; lab[v] = u; } void sol() { cin >> n; fill_n(lab, n*2+4, -1); for(int i = 1; i <= n; i ++) { cin >> p[i].fi >> p[i].se; } sort(p+1, p+1+n); set<pll> st; for(int i = 1; i <= n; i ++) { auto l = st.lower_bound({p[i].fi, 0ll}), r = st.upper_bound({p[i].se, n*2+1}); if(l != st.end() && r != st.begin() && (*l).fi < p[i].se) { r = prev(r); while(true) { pll x = *l; ll u = findp(i), v = findp(x.se+n); if(u != v)hop(u, v); u = findp(i+n), v = findp(x.se); if(u != v)hop(u, v); if(l == r) break; ++l; } } st.insert({p[i].se, i}); } for(int i = 1; i <= n*2; i ++) { if(i <= n && findp(i) == findp(i+n)) { cout << 0; return; } if(lab[i] < 0)++ans; } cout << pw(2, ans/2); } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int test = 1; //cin >> test; while (test-- > 0) sol(); 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...