이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
const int N = 1000001;
int n, p[N << 1], sz[N << 1], conn = 0, ans = 1, clr[N << 1];
vector<int> f;
set<int> disc;
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];
}
struct SegTree {
int size = 1;
vector<pair<int, int>> seg;
void init(int _n) {
for (; size < _n;) size *= 2;
seg.assign(2 * size + 10, {0, 0});
}
void update(int pos, int v, int l, int r, int id, bool d = 0) {
if (l == r) {
if (!d) {
seg[id].first = 1;
seg[id].second = v;
} else seg[id].first = seg[id].second = 0;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(pos, v, l, mid, id * 2, d);
else update(pos, v, mid + 1, r, id * 2 + 1, d);
seg[id].first = seg[id * 2].first + seg[id * 2 + 1].first;
}
void dive(int i, int qr, int l, int r, int id) {
if (qr < l || r < 1 || l > r || !seg[id].first) return;
if (l == r) {
merge(i, seg[id].second + n);
merge(i + n, seg[id].second);
if (find(i) == find(i + n) || find(seg[id].second) == find(seg[id].second + n)) {
cout << "0\n";
exit(0);
}
return;
}
int mid = (l + r) / 2;
if (seg[id * 2].first) dive(i, qr, l, mid, id * 2);
if (seg[id * 2 + 1].first) dive(i, qr, mid + 1, r, id * 2 + 1);
}
} st;
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i <= (n << 1); i++) p[i] = i, sz[i] = 1;
vector<pair<int, int>> p(n);
for (auto& [x, y] : p) {
cin >> x >> y;
clr[y] = 1;
}
sort(p.begin(), p.end());
st.init(2 * n + 1);
for (int i = 0; i < n; i++) {
if (i) for (int j = p[i - 1].first; j < p[i].first; j++) {
if (clr[j]) {
st.update(j, 0, 1, 2 * n, 1, 1);
}
}
st.dive(i + 1, p[i].second - 1, 1, 2 * n, 1);
st.update(p[i].second, i + 1, 1, 2 * n, 1);
}
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);
}
conn = disc.size();
for (int i = 1; i <= conn; i++) ans = ans * 2 % mod;
cout << ans << '\n';
}
# | 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... |