Submission #1216747

#TimeUsernameProblemLanguageResultExecution timeMemory
1216747GrayPort Facility (JOI17_port_facility)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned ll #define ld long double #define ff first #define ss second #define ln "\n" const ll MOD = 1e9+7; struct DSU{ vector<ll> p; vector<map<ll, ll>> nodes; ll n, cnt; DSU(ll N){ n=N; cnt=N; p.resize(n, -1); nodes.resize(n); for (ll i=0; i<n; i++) nodes[i][i]=0; } ll get(ll x){ return p[x]==-1?x:p[x]=get(p[x]); } bool unite(ll u, ll v){ ll iu=u, iv=v; u=get(u); v=get(v); if (u==v){ return nodes[u][iu]!=nodes[v][iv]; } if (nodes[u].size()<nodes[v].size()) swap(u, v); p[v]=u; if (nodes[u][u]==nodes[v][v]){ for (auto &[x, val]:nodes[v]){ val^=1; } } for (auto [x, val]:nodes[v]) nodes[u][x]=val; cnt--; return 1; } }; void solve(){ ll n; cin >> n; vector<ll> a(2*n+1); vector<array<ll, 2>> rng(n); for (ll i=0; i<n; i++){ ll l, r; cin >> l >> r; a[l]=i; a[r]=i; rng[i] = {l, r}; } set<array<ll, 2>> present; DSU tr(n); for (ll i=1; i<=2*n; i++){ if (!present.count({rng[a[i]][1], a[i]})){ for (auto [r, ind]:present){ if (r>rng[a[i]][1]) break; if (!tr.unite(ind, a[i])){ cout << 0 << ln; return; } } // if(col[a[i]]==-1) col[a[i]]=0; present.insert({rng[a[i]][1], a[i]}); }else{ present.erase({rng[a[i]][1], a[i]}); } } ll res=1; for (ll i=0; i<tr.cnt; i++){ res=(res*2)%MOD; } cout << res << ln; } int main(){ ios_base::sync_with_stdio(0); cin.tie(nullptr); ll t=1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...