이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 {
set<pair<int, 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].insert({b[i], 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].begin());
active.erase(el);
}
}
void addAll(int x) {
x = find(x);
forn(col, 2) {
if(comp[x].color[col].empty()) {continue;}
auto el = *(comp[x].color[col].begin());
active.insert(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].insert(it);
}
comp[y].color[col].clear();
}
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]].erase({b[x], x});
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);
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;
}
init();
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |