제출 #482464

#제출 시각아이디문제언어결과실행 시간메모리
482464hidden1Port Facility (JOI17_port_facility)C++14
22 / 100
6088 ms145088 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #ifndef LOCAL #define cerr if(false) cerr #endif #define endl "\n" #define all(x) (x).begin(), (x).end() #define forn(i, n) for(int i = 0; i < n; i ++) #define revn(i, n) for(int i = n - 1; i >= 0; i --) typedef long long ll; template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;} template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;} template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;} template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;} template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const ll mod = 1e9 + 7; const int MAX_N = 1e6 + 10; int par[MAX_N]; int dist[MAX_N]; int n; int a[MAX_N], b[MAX_N]; int who[2 * MAX_N]; struct Comp { vector<int> color[2]; vector<int> all; int size() { return all.size(); } } comp[MAX_N]; void init() { for(int i = 0; i < MAX_N; i ++) { comp[i].color[0].push_back(i); comp[i].all.push_back(i); par[i] = i; dist[i] = 0; } } int find(int x) { if(x == par[x]) { return x; } else { return par[x] = find(par[x]); } } set<pair<int, int> > active; void removeAll(int x) { x = find(x); forn(col, 2) { if(comp[x].color[col].empty()) {continue;} auto el = comp[x].color[col].back(); auto it = active.find({b[el], el}); if(it != active.end()) { active.erase(it); } } } void addAll(int x) { x = find(x); forn(col, 2) { if(comp[x].color[col].empty()) {continue;} auto el = comp[x].color[col].back(); active.insert({b[el], el}); } } vector<pair<int, int> > merged; void merge(int x, int y) { int xx = x, yy = y; merged.push_back({x, y}); x = find(x); y = find(y); if(x == y) { if(dist[xx] == dist[yy]) { cout << 0 << endl; exit(0); } else { return; } } if(comp[x].size() < comp[y].size()) { swap(x, y); swap(xx, yy); } removeAll(x); removeAll(y); int xr = dist[xx] ^ dist[yy] ^ 1; forn(col, 2) { for(auto it : comp[y].color[col]) { comp[x].color[col ^ xr].push_back(it); } comp[y].color[col].resize(0); sort(all(comp[x].color[col ^ xr]), [](const int x, const int y) { return b[x] > b[y]; }); } for(auto it : comp[y].all) { dist[it] ^= xr; par[it] = x; comp[x].all.push_back(it); } addAll(x); } void remove(int x) { int p = find(x); removeAll(p); comp[p].color[dist[x]].pop_back(); addAll(p); } void add(int x) { vector<int> toMerge = {}; for(auto it : active) { if(it.first >= b[x]) { break; } else { toMerge.push_back(it.second); } } if(toMerge.empty()) { addAll(x); } else { for(auto it : toMerge) { merge(x, it); } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); init(); cin >> n; for(int i = 1; i <= n; i ++) { cin >> a[i] >> b[i]; a[i] --; b[i] --; who[a[i]] = i; who[b[i]] = -i; } for(int i = 0; i < 2 * n; i ++) { if(who[i] < 0) { remove(-who[i]); } else { add(who[i]); } } ll pw = 1; for(int i = 1; i <= n; i ++) { if(par[i] == i) { pw = (pw * 2ll) % mod; } } cout << pw << endl; 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...