제출 #162940

#제출 시각아이디문제언어결과실행 시간메모리
162940combi1k1Port Facility (JOI17_port_facility)C++14
22 / 100
6090 ms8816 KiB
#include<bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i = a ; i < b ; ++i) const int N = 2e6 + 1; typedef pair<int,int> ii; int p[N]; int s[N]; int lead(int x) { return p[x] == x ? x : p[x] = lead(p[x]); } int join(int x,int y) { x = lead(x); y = lead(y); if (x == y) return 0; if (s[x] < s[y]) swap(x,y); p[y] = x; s[x] += s[y]; return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector<ii> vec; FOR(i,0,n) { int x; cin >> x; int y; cin >> y; vec.push_back(ii(x,y)); p[i] = i; p[i + n] = i + n; s[i] = 1; s[i + n] = 1; } sort(vec.begin(),vec.end()); map<int,int> mp; FOR(i,0,n) { auto it1 = mp.lower_bound(vec[i].first); auto it2 = mp.upper_bound(vec[i].second); if (it2 != mp.begin()) for(; it1 != it2 ; ++it1) { join(i,n + it1 -> second); join(i + n,it1 -> second); } mp[vec[i].second] = i; } int ans = 1; FOR(i,0,n) { if (lead(i) == lead(i + n)) ans = 0; if (lead(i) == i) ans *= 2, ans %= 1000000007; } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...