제출 #77663

#제출 시각아이디문제언어결과실행 시간메모리
77663szawinisPort Facility (JOI17_port_facility)C++17
0 / 100
5 ms4472 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 r < rhs.r; } }; int n; vector<seg> a; int dsu[N]; int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); } void merge(int u, int v) { if((u = root(u)) == (v = root(v))) return; dsu[u] += dsu[v]; dsu[v] = u; } 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); } fill(dsu, dsu+N, -1); sort(a.begin(), a.end()); priority_queue<pair<seg, int> > pq; for(seg s: a) { pair<seg, int> add = {s, -1}; while(!pq.empty() && pq.top().first.r > s.l) { if(a[pq.top().first.i].l < s.l && pq.top().second > s.l) cout << 0, exit(0); if(pq.top().first.l < s.l) { add.first.l = min(pq.top().first.l, add.first.l); add.second = max(pq.top().first.r, add.second); merge(pq.top().first.i, s.i); } pq.pop(); } pq.push(add); } 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...