제출 #897589

#제출 시각아이디문제언어결과실행 시간메모리
897589andrey27_smPort Facility (JOI17_port_facility)C++17
10 / 100
13 ms2760 KiB
//#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("arch=icelake-server,avx512f,avx512bw,avx512bitalg,bmi,bmi2") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; constexpr ll mod = 1e9 + 7; ll bin_pow(ll base, ll exp) { ll res = 1; while (exp){ if (exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } int sgt[8000000]; int min_r[8000000]; /* void update(int v, int tl, int tr, int pos, int val) { if (tl == tr) sgt[v] = val; else { int tm = (tl + tr) / 2; if (pos <= tm) update(v * 2, tl, tm, pos, val); else update(v * 2 + 1, tm + 1, tr, pos, val); sgt[v] = sgt[v * 2] + sgt[v * 2 + 1]; } } int get(int v, int l, int r, int tl, int tr) { if (l > tr or tl > r) return 0; if (tl <= l && r <= tr) return sgt[v]; int m = (l + r) / 2; return get(v * 2, l, m, tl, tr) + get(v * 2 + 1, m + 1, r, tl, tr); }*/ struct dsu { vector<int> p; vector<int> sz; int szz; dsu() {} dsu(int n) { p.resize(n); sz.resize(n); for(int i = 0;i < n;i++) { p[i] = i; sz[i] = 1; } szz = n; } int get(int v) { if(p[v] == v) { return v; } return p[v] = get(p[v]); } void unite(int a,int b) { a = get(a); b = get(b); if(a == b) return; szz--; if(sz[a] < sz[b]) { swap(a,b); } p[b] = a; sz[a]+=sz[b]; } } D; void update(int v,int l,int r,int pos, int val) { sgt[pos] = val; } int get(int v, int l, int r, int tl, int tr) { int sum = 0; vector<int> to_rem; for(int i = tl;i <= tr;i++) { sum+=sgt[i]; if(sgt[i]) { to_rem.push_back(i); D.unite(tl, i); } sgt[i] = 0; } if(to_rem.size()) { sgt[to_rem[0]] = 1; sgt[to_rem.back()] = 1; } return sum; } int main() { //ios_base::sync_with_stdio(false); //cin.tie(nullptr); //cout.tie(nullptr); ll n; cin >> n; D = dsu(2*n+1); vector<pair<int,int>> events; for (int i = 0; i < n; ++i) { int l,r; cin >> l >> r; events.emplace_back(l,r); events.emplace_back(r,l); D.unite(l,r); } sort(events.begin(),events.end()); bool is_pos = true; int cnt = n; set<int> Rs; set<int> Ls; for(int i = 0;i < 2*n;i++) { if(events[i].first < events[i].second) { Ls.insert(events[i].first); auto it = Rs.insert(events[i].second); if(it.first != Rs.begin()) { min_r[events[i].first] = *prev(it.first); } update(1,1,2*n,events[i].first,1); } else { update(1,1,2*n,events[i].second,0); Rs.erase(events[i].first); auto it = Ls.find(events[i].second); if(it != Ls.end()) { it++; if(it != Ls.end() and *it < min_r[events[i].second]) { is_pos = false; break; } it--; } Ls.erase(it); get(1,1,2*n,events[i].second,events[i].first); } } cnt = D.szz-1; if(is_pos) { cout << bin_pow(2,cnt) << '\n'; } else { cout << 0 << '\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...