이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 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, 0, sizeof st); }
void build(int v = 1, int l = 0, int r = 2 * n) {
st[v] = -INF;
if (l != r) {
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
st[v] = -INF;
}
}
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 -INF;
} 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));
}
}
};
// 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, -INF);
right_end.upd(pts[x].first, -INF);
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;
}
left_end.build();
right_end.build();
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)) {
ll ans = 1;
for (int i = 0; i < cnt; i++) {
ans += ans;
if (ans >= MOD) ans -= MOD;
}
cout << ans << '\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... |