제출 #77547

#제출 시각아이디문제언어결과실행 시간메모리
77547szawinisPort Facility (JOI17_port_facility)C++17
0 / 100
61 ms53880 KiB
#include <bits/stdc++.h> #define long long long using namespace std; const long MOD = 1e9+7; const int N = 1 << 20; struct seg { int l, r, i; seg() { l = r = i = MOD; } seg(int l, int r, int i): l(l), r(r), i(i) {} bool operator<(const seg& rhs) const { return l < rhs.l; } bool operator==(const seg& rhs) const { if(l == rhs.l) { assert(i == rhs.i); return true; } return false; } }; pair<seg, seg> merge(pair<seg, seg> a, pair<seg, seg> b) { seg mn1 = seg(), mn2 = seg(); mn1 = min(a.first, b.first); if(mn1 == a.first) mn2 = min(a.second, min(b.first, b.second)); else mn2 = min(b.second, min(a.first, a.second)); return make_pair(mn1, mn2); } int n; vector<seg> a; pair<seg, seg> t[N << 1]; void update(int i, seg v) { i += N; t[i] = merge({v, seg()}, t[i]); while(i >>= 1) t[i] = merge(t[i << 1], t[i << 1 | 1]); } pair<seg, seg> query(int l, int r) { pair<seg, seg> ret = {seg(), seg()}; for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) { if(l & 1) ret = merge(t[l++], ret); if(r & 1) ret = merge(t[--r], ret); } return ret; } int dsu[N]; int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 0, x, y; i < n; i++) { cin >> x >> y; --x, --y; a.emplace_back(x, y, i); } for(int i = 1; i < 2*N; i++) t[i] = {seg(), seg()}; sort(a.begin(), a.end(), [] (auto x, auto y) { return x.r < y.r; }); fill(dsu, dsu+N, -1); for(seg s: a) { auto res = query(s.l+1, s.r-1); // cout << s.l << ' ' << s.r << " pair res" << res.first.l << ' ' << res.second.l << endl; if(res.second.l < s.l) cout << 0, exit(0); update(s.r, s); int u = s.i, v = res.first.i; if(v != MOD && res.first.l < s.l && (u = root(u)) != (v = root(v))) { dsu[u] += dsu[v]; dsu[v] = u; } } long ans = 1; for(int i = 0; i < n; i++) if(root(i) == i) ans = ans * 2 % MOD; 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...