This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int N = (1 << 21) + 10;
int p[2 * N], sz[2 * N], pt[2 * N], a[N], b[N], cc = 0;
set<int> disc;
vector<int> seg[2 * N];
ll ans = 1;
int n;
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
}
void update(int pos, int val, int l = 1, int r = 2 * n, int id = 1) {
seg[id].push_back(val);
if (l == r) return;
int mid = (l + r) / 2;
if (pos <= mid) update(pos, val, l, mid, id * 2);
else update(pos, val, mid + 1, r, id * 2 + 1);
}
void query(int ql, int qr, int val, int l = 1, int r = 2 * n, int id = 1) {
if (ql > qr || qr < l || r < ql || seg[id].empty()) return;
if (ql <= l && r <= qr) {
merge(val, seg[id][0] + n);
merge(val + n, seg[id][0]);
for (int i = pt[id] + 1; i < seg[id].size(); i++) {
merge(seg[id][i-1], seg[id][i]);
merge(seg[id][i-1] + n, seg[id][i] + n);
pt[id]++;
}
return;
}
int mid = (l + r) / 2;
query(ql, qr, val, l, mid, id * 2);
query(ql, qr, val, mid + 1, r, id * 2 + 1);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
vector<int> idx;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
idx.push_back(i);
}
iota(p, p + 2 * N, 0);
fill(sz, sz + 2 * N, 1);
sort(idx.begin(), idx.end(), [&] (auto x, auto y) {
return a[x] < a[y];
});
for (int i : idx) {
query(a[i], b[i], i);
update(b[i], i);
}
for (int i = 1; i <= n; i++) {
if (find(i) == find(i + n)) {
cout << "0\n";
return 0;
}
}
for (int i = 1; i <= 2 * n; i++) {
int x = find(i);
if (x > n) x -= n;
disc.insert(x);
}
int sz = (int) disc.size();
while (sz--) (ans *= 2LL) %= mod;
cout << ans << '\n';
}
Compilation message (stderr)
port_facility.cpp: In function 'void query(int, int, int, int, int, int)':
port_facility.cpp:40:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i = pt[id] + 1; i < seg[id].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
# | 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... |