Submission #975739

#TimeUsernameProblemLanguageResultExecution timeMemory
975739starchanPort Facility (JOI17_port_facility)C++17
78 / 100
1817 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; #define in array<int, 2> #define pb push_back #define pob pop_back #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) const int SMX = 1e6+5; const int MX = 2e6+3; const int LMX = 3e7; const int mod = 1e9+7; vector<vector<int>> g; int leaf[MX]; vector<int> lleft; vector<int> rright; vector<bool> tree; int nxt = 0; int New() { lleft.pb(-1); rright.pb(-1); g.resize(g.size()+1); tree.pb(0); return nxt++; } int build(int l, int r) { int id = New(); int m = (l+r)/2; if(l==r) return id; lleft[id] = build(l, m); rright[id] = build(m+1, r); tree[id] = 0; return id; } int upd(int pos, int id, int l, int r) { int id_n = New(); tree[id_n] = 1; if(l == r) return leaf[pos] = id_n; lleft[id_n] = lleft[id]; rright[id_n] = rright[id]; int m = (l+r)/2; if(pos <= m) lleft[id_n] = upd(pos, lleft[id], l, m); else rright[id_n] = upd(pos, rright[id], m+1, r); return id_n; } void add(int pp, int ql, int qr, int id, int l, int r) { if(qr < l || r < ql) return; if((ql <= l) && (r <= qr)) { g[pp].pb(id); return; } int m = (l+r)/2; add(pp, ql, qr, lleft[id], l, m); add(pp, ql, qr, rright[id], m+1, r); return; } vector<int> pa; vector<bool> col; bool works = true; int leader(int u) { if(pa[u] < 0) return u; else { int p = leader(pa[u]); col[u] = col[u]^col[pa[u]]; return pa[u] = p; } } void merge(int u, int v, int xr) { int x = leader(u); int y = leader(v); if(x == y) { if(col[u]^col[v]^xr) works = false; return; } if(pa[x] < pa[y]) { swap(x, y); swap(u, v); } pa[y]+=pa[x]; pa[x] = y; col[x] = col[u]^col[v]^xr; return; } bitset<LMX> vis, ppl; void dfs(int u) { vis[u] = 1; if(lleft[u] != -1) { if((!vis[lleft[u]]) && tree[lleft[u]]) dfs(lleft[u]); if((!vis[rright[u]]) && tree[rright[u]]) dfs(rright[u]); if(tree[lleft[u]]){ //cout << "cat_L_Calling " << lleft[u] << " from " << u << endl; merge(u, lleft[u], 0);} if(tree[rright[u]]){ //cout << "cat_R_Calling " << rright[u] << " from " << u << endl; merge(u, rright[u], 0);} return; } for(int v: g[u]) { if(!tree[v]) continue; merge(u, v, 1); if(vis[v]) { //cout << "Tried to call " << v << " from " << u << endl; continue; } //cout << "Calling " << v << " from " << u << "\n"; dfs(v); } return; } signed main() { fast();//During debugging, this should ideally be removed. int n; cin >> n; vector<in> vv(n+1); for(int i = 1; i <= n; i++) cin >> vv[i][0] >> vv[i][1]; sort(vv.begin()+1, vv.end()); int sn = 0; int root = build(1, 2*n); //cout << "nxt = " << nxt << endl; int b[n+1]; for(int i = 1; i <= n; i++) { root = upd(vv[i][1], root, 1, 2*n); add(leaf[vv[i][1]], vv[i][0], vv[i][1]-1, root, 1, 2*n); b[++sn] = leaf[vv[i][1]]; //cout << "b[sn] = " << b[sn] << endl; } int N = g.size(); pa.assign(N, -1); col.assign(N, 0); for(int i = 1; i <= n; i++) dfs(b[i]); if(!works) { cout << "0\n"; return 0; } int ans = 1; for(int i = 1; i <= n; i++) { if(ppl[leader(b[i])]) continue; ppl[leader(b[i])] = 1; ans*=2; ans%=mod; } cout << ans << "\n"; 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...