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 <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <numeric>
#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define NINF 0xc0c0c0c0
#define INFLL 0x3f3f3f3f3f3f3f3f
// change if necessary
#define MAXN 1000010
using namespace std;
int n;
pair<int, int> pts[MAXN];
int l_inv[MAXN];
int r_inv[MAXN];
int vis[MAXN]; // 0 unvis, 1 in first stack, 2 in second stack
struct segtree {
int st[8 * MAXN];
segtree() { memset(st, NINF, sizeof st); }
void upd(int x, int y, int v = 1, int l = 0, int r = 2 * n) {
if (l == r) {
st[v] = y;
} else {
int m = (l + r) / 2;
if (x <= m) {
upd(x, y, 2 * v, l, m);
} else {
upd(x, y, 2 * v + 1, m + 1, r);
}
st[v] = max(st[2 * v], st[2 * v + 1]);
}
}
int qry(int x, int y, int v = 1, int l = 0, int r = 2 * n) {
if (r < x || l > y) {
return NINF;
} else if (x <= l && r <= y) {
return st[v];
} else {
int m = (l + r) / 2;
return max(qry(x, y, 2 * v, l, m), qry(x, y, 2 * v + 1, m + 1, r));
}
}
};
ll modpow(ll x, ll e) {
ll res = 1;
while (e) {
if (e & 1) res = res * x % MOD;
x = x * x % MOD;
e >>= 1;
}
return res;
}
// left_end is min left end whose right is within a given range
// right_end is max right end whose left is within a given range
segtree left_end, right_end;
void dfs(int x, int c) {
left_end.upd(pts[x].second, NINF);
right_end.upd(pts[x].first, NINF);
vis[x] = c;
while (-left_end.qry(pts[x].first, pts[x].second) < pts[x].first) {
int left_loc = l_inv[-left_end.qry(pts[x].first, pts[x].second)];
dfs(left_loc, 3 - c);
}
while (right_end.qry(pts[x].first, pts[x].second) > pts[x].second) {
int right_loc = r_inv[right_end.qry(pts[x].first, pts[x].second)];
dfs(right_loc, 3 - c);
}
}
int cur_stack[MAXN];
int r = 0;
bool check(const vector<pair<int, int>> &v) {
vector<int> tot;
for (auto p : v) {
tot.push_back(p.first);
tot.push_back(p.second);
}
sort(tot.begin(), tot.end());
for (int x : tot) {
if (l_inv[x] != -1) {
cur_stack[r++] = l_inv[x];
} else {
if (r == 0 || cur_stack[r - 1] != r_inv[x]) {
return false;
}
r--;
}
}
return true;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
memset(l_inv, -1, sizeof l_inv);
memset(r_inv, -1, sizeof r_inv);
for (int i = 0; i < n; i++) {
int a, b; cin >> a >> b;
pts[i] = {a, b};
l_inv[a] = i;
r_inv[b] = i;
}
for (int i = 0; i < n; i++) {
left_end.upd(pts[i].second, -pts[i].first);
right_end.upd(pts[i].first, pts[i].second);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
cnt++;
dfs(i, 1);
}
}
vector<pair<int, int>> a, b;
for (int i = 0; i < n; i++) {
if (vis[i] == 1) {
a.push_back(pts[i]);
} else {
b.push_back(pts[i]);
}
}
if (check(a) && check(b)) {
cout << modpow(2, cnt) << '\n';
} else {
cout << "0\n";
}
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... |