This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
struct datas {
int x, y, id;
bool operator<(const datas &a) {
return x < a.x;
}
};
vector<datas> ori, v, tv;
vector<int> e[1000100];
vector<int> C;
int n;
int find(int a) {
if(C[a] != a) return C[a] = find(C[a]);
return a;
}
void merge(int a, int b) {
// cout << a << ' ' << b << '\n';
a = find(a);
b = find(b);
if(a == b) return;
if(a > b) swap(a, b);
C[b] = a;
}
void merge_sort(int l, int r) {
if(l == r) return;
int m = l + r >> 1, tl = l, tr = m + 1, now = -1;
merge_sort(l, m);
merge_sort(m + 1, r);
for(int i = l; i <= r; i++) {
if(tr > r || (tl <= m && v[tl].y < v[tr].y)) {
if(now == -1 || (ori[now].y < v[tl].y)) {
now = v[tl].id;
}
tv[i] = v[tl];
tl++;
} else {
if(now != -1 && v[tr].x < ori[now].y) {
e[v[tr].id].pb(now);
e[now].pb(v[tr].id);
// cout << ">> " << now << ' ' << v[tr].id << '\n';
merge(v[tr].id, now + n);
merge(now, v[tr].id + n);
}
tv[i] = v[tr];
tr++;
}
}
for(int i = l; i <= r; i++)
v[i] = tv[i];
}
bitset<1000100> vis;
vector<datas> lv, rv;
void dfs(int a, int c) {
vis[a] = 1;
if(c == 1)
lv.pb(ori[a]);
else
rv.pb(ori[a]);
for(int i : e[a])
if(!vis[i])
dfs(i, 3 - c);
}
int main() {Tie
cin >> n;
v.resize(n), tv.resize(n), C.resize(n * 2);
for(int i = 0; i < n; i++) {
cin >> v[i].x >> v[i].y;
v[i].id = i;
}
for(int i = 0; i < n * 2; i++)
C[i] = i;
ori = v;
sort(ALL(v));
merge_sort(0, n - 1);
for(int i = 0; i < n; i++) {
v[i].x = n * 2 + 1 - v[i].x;
v[i].y = n * 2 + 1 - v[i].y;
swap(v[i].x, v[i].y);
ori[i].x = n * 2 + 1 - ori[i].x;
ori[i].y = n * 2 + 1 - ori[i].y;
swap(ori[i].x, ori[i].y);
}
sort(ALL(v));
merge_sort(0, n - 1);
int ans = 1;
vector<vector<int>> con(n * 2);
// for(int i = 0; i < n * 2; i++)
// cout << find(i) << ' ';
// cout << '\n';
for(int i = 0; i < n; i++) {
if(vis[i]) continue;
lv.clear();
rv.clear();
dfs(i, 1);
sort(ALL(lv));
int mx = -1;
for(datas i : lv) {
if(i.y > mx && mx > i.x)
ans = 0;
mx = max(mx, i.y);
}
sort(ALL(rv));
mx = -1;
for(datas i : rv) {
if(i.y > mx && mx > i.x)
ans = 0;
mx = max(mx, i.y);
}
}
int tmp = 0;
for(int i = 0; i < 2 * n; i++)
if(find(i) == i)
tmp++;
tmp >>= 1;
for(int i = 0; i < tmp; i++)
ans = (ans << 1) % 1000000007;
cout << ans << '\n';
}
Compilation message (stderr)
port_facility.cpp: In function 'void merge_sort(int, int)':
port_facility.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int m = l + r >> 1, tl = l, tr = m + 1, now = -1;
| ~~^~~
# | 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... |