#include "bits/stdc++.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
const ll N = 1 << 20, mod = 1e9 + 7;
struct node {
ll f, o;
set<ll> s;
};
ll n, l[N], r[N], c[N], p[N], id[2 * N], ans = 1, rr[2 * N];
node t[4 * N];
queue<ll> q;
void build(ll v, ll l1, ll r1) {
if (l1 + 1 == r1) {
if (id[l1] != -1) {
t[v].s.insert(r[id[l1]]);
}
return;
}
ll m = (l1 + r1) / 2;
build(v * 2, l1, m), build(v * 2 + 1, m, r1);
for (auto x: t[v * 2].s) t[v].s.insert(x);
for (auto x: t[v * 2 + 1].s) t[v].s.insert(x);
}
void build() {
build(1, 0, 2 * N);
}
void add3(ll v, ll l1, ll r1, ll L, ll R, ll x, ll i) {
if (l1 >= L || r1 <= 0) return;
if (l1 >= 0 && r1 <= L) {
auto it = t[v].s.lower_bound(L);
while (it != t[v].s.end() && *it < R) {
if (!c[rr[*it]]) c[rr[*it]] = x, q.push(rr[*it]);
t[v].s.erase(it);
it = t[v].s.lower_bound(L);
}
return;
}
ll m = (l1 + r1) / 2;
add3(v * 2, l1, m, L, R, x, i);
add3(v * 2 + 1, m, r1, L, R, x, i);
}
void add3(ll l1, ll r1, ll x, ll i) {
add3(1, 0, 2 * N, l1, r1, x, i);
}
void add4(ll v, ll l1, ll r1, ll L, ll R) {
if (l1 > L || r1 <= L) return;
t[v].f = max(t[v].f, R);
if (l1 + 1 == r1) return;
ll m = (l1 + r1) / 2;
add4(v * 2, l1, m, L, R);
add4(v * 2 + 1, m, r1, L, R);
}
void add4(ll L, ll R) {
add4(1, 0, 2 * N, L, R);
}
void add1(ll v, ll l1, ll r1, ll L, ll R, ll x, ll i) {
if (l1 >= R || r1 <= L) return;
if (l1 >= L && r1 <= R) {
while (t[v].s.size() && (*--t[v].s.end()) > R) {
if (!c[rr[(*--t[v].s.end())]]) c[rr[(*--t[v].s.end())]] = x, q.push(rr[(*--t[v].s.end())]);
t[v].s.erase(--t[v].s.end());
}
return;
}
ll m = (l1 + r1) / 2;
add1(v * 2, l1, m, L, R, x, i);
add1(v * 2 + 1, m, r1, L, R, x, i);
}
void add1(ll l1, ll r1, ll x, ll i) {
add1(1, 0, 2 * N, l1, r1, x, i);
}
void add2(ll v, ll l1, ll r1, ll L, ll R) {
if (l1 >= R || r1 <= L) return;
if (l1 >= L && r1 <= R) {
t[v].o = min(t[v].o, R);
return;
}
ll m = (l1 + r1) / 2;
add2(v * 2, l1, m, L, R);
add2(v * 2 + 1, m, r1, L, R);
}
void add2(ll l1, ll r1) {
add2(1, 0, 2 * N, l1, r1);
}
bool check(ll v, ll l1, ll r1) {
if (t[v].o < t[v].f) {
return 0;
}
if (l1 + 1 == r1) return 1;
ll m = (l1 + r1) / 2;
return check(v * 2, l1, m) & check(v * 2 + 1, m, r1);
}
bool check() {
return check(1, 0, 2 * N);
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
n = 1e6;
cin >> n;
memset(id, -1, sizeof id);
for (ll i = 0; i < n; i++) {
l[i] = 1, r[i] = 2 * n;
cin >> l[i] >> r[i];
id[l[i]] = i, rr[r[i]] = i;
}
build();
iota(p, p + n, 0);
sort(p, p + n, [&](ll x, ll y) { return l[x] < l[y]; });
for (ll _ = 0; _ < n; _++) {
if (q.size()) {
ll i = q.front();
q.pop();
add1(l[i], r[i], 3 - c[i], i);
add3(l[i], r[i], 3 - c[i], i);
// add4(l[i], r[i], c[i]);
_--;
} else {
ll i = p[_];
if (c[i]) continue;
ans = (ans * 2) % mod;
c[i] = 1;
add1(l[i], r[i], 3 - c[i], i);
add3(l[i], r[i], 3 - c[i], i);
// add4(l[i], r[i], c[i]);
}
}
for (ll i = 0; i < 4 * N; i++) t[i].s.clear();
sort(p, p + n, [&](ll x, ll y) { return r[x] < r[y]; });
// for (ll _ = 0; _ < n; _++) {
// ll i = p[_];
// add2(l[i], r[i], 3 - c[i]);
// }
// for (ll i = 0; i < n; i++) ans = (ans * (1 + (find_set(i) == i))) % mod;
for (ll x = 1; x <= 2; x++) {
for (ll i = 0; i < 4 * N; i++) t[i].o = 1e9, t[i].f = -1;
for (ll i = 0; i < n; i++) {
if (c[i] == x) add4(l[i], r[i]), add2(l[i], r[i]);
}
ans *= check();
}
cout << ans;
}
# | 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... |