#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define bigint __int128 #define emb emplace_back #define pb push_back #define pii pair <int, int> #define fi first #define se second #define all(v) v.begin(), v.end() #define Task "" #define MASK(k) (1ull << k) #define bitcnt(k) __builtin_popcount(k) #define testBit(n, k) ((n >> k) & 1) #define flipBit(n, k) (n ^ (1ll << k)) #define offBit(n, k) (n & ~MASK(k)) #define onBit(n, k) (n | (1ll << k)) template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;} template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;} const int N = 1e6 + 5, LG = 20, mod = 1e9 + 7; const ll INF = 1e18; int n; pii range[N]; namespace sub2 { vector <int> adj[N]; int color[N]; bool dfs(int u, int c) { color[u] = c; for (int v: adj[u]) { if (color[v] == color[u]) return false; if (color[v] == 0) { bool check = dfs(v, 3 - c); if (!check) return false; } } return true; } ll solve() { sort (range + 1, range + n + 1); for (int u = 1; u <= n; u++) { for (int v = u + 1; v <= n; v++) { if (range[v].fi < range[u].se && range[u].se < range[v].se) { adj[u].emplace_back(v); adj[v].emplace_back(u); } } } int ans = 1; for (int u = 1; u <= n; u++) if (!color[u]) { bool check = dfs(u, 1); if (!check) return 0; ans = ans * 2 % mod; } return ans; } } namespace sub34 { struct DSU { vector <int> lab; int components; DSU (int n) { lab.assign(n + 1, -1); components = n; } int find_set(int u) { return lab[u] < 0 ? u : lab[u] = find_set(lab[u]); } bool unite(int u, int v) { u = find_set(u); v = find_set(v); if (u == v) return false; if (lab[u] > lab[v]) swap(u, v); lab[u] += lab[v]; lab[v] = u; --components; return true; } }; struct SegmentTree { vector <int> st; SegmentTree (int n) { st.assign(n * 4 + 5, 1e9); } void update(int id, int l, int r, int p, int val) { if (l == r) { st[id] = val; return; } int mid = (l + r) >> 1; if (p <= mid) update(id << 1, l, mid, p, val); else update(id << 1 | 1, mid + 1, r, p, val); st[id] = min(st[id << 1], st[id << 1 | 1]); } int get(int id, int l, int r, int u, int v) { if (u > r || v < l) return 1e9; if (u <= l && r <= v) return st[id]; int mid = (l + r) >> 1; return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } }; struct SuperSegmentTree { vector <int> st; vector <bool> lazy; SuperSegmentTree (int n) { st.assign(n * 4 + 5, 0); lazy.assign(n * 4 + 5, false); } void push_down(int id) { if (lazy[id]) { st[id << 1] = st[id << 1 | 1] = st[id]; lazy[id << 1] = lazy[id << 1 | 1] = true; lazy[id] = false; } } void update(int id, int l, int r, int u, int v, int val) { if (u > r || v < l) return; if (u <= l && r <= v) { st[id] = val; lazy[id] = true; return; } int mid = (l + r) >> 1; push_down(id); update(id << 1, l, mid, u, v, val); update(id << 1 | 1, mid + 1, r, u, v, val); } int get(int p) { int id = 1, l = 1, r = n; while (l < r) { int mid = (l + r) >> 1; push_down(id); if (p <= mid) id <<= 1, r = mid; else id = id << 1 | 1, l = mid + 1; } return st[id]; } }; int nearAffect[N], limit[N]; bool cmp(int u, int v) { return range[u].se > range[v].se; } ll solve() { sort (range + 1, range + n + 1); for (int i = 1; i <= n; i++) { int low = i + 1, high = n, lim = -1; while (low <= high) { int mid = (low + high) >> 1; if (range[mid].fi < range[i].se) low = (lim = mid) + 1; else high = mid - 1; } limit[i] = lim; } stack <int> st; for (int i = n; i > 0; i--) { while (!st.empty() && range[i].se > range[st.top()].se) st.pop(); nearAffect[i] = (st.empty() ? -1 : st.top()); if (nearAffect[i] > limit[i]) nearAffect[i] = -1; st.emplace(i); } // check exist answer SegmentTree ST(n); for (int i = 1; i <= n; i++) if (nearAffect[i] != -1) { ST.update(1, 1, n, i, nearAffect[i]); } for (int i = 1; i <= n; i++) if (limit[i] != -1) { int k = ST.get(1, 1, n, i + 1, limit[i]); if (k <= limit[i]) return 0; } // vector <int> order(n); iota(all(order), 1); sort (all(order), cmp); DSU dsu(n); set <int> s; // SuperSegmentTree nxt(n), back(n); vector <int> nxt(n + 1, 1e9); for (int i: order) { auto it = s.upper_bound(i); if (it != s.begin()) nxt[*prev(it)] = i; if (it != s.end()) nxt[i] = *it; s.emplace(i); if (limit[i] != -1) { // noi canh i->j (i < j <= limit[i] && B[i] < B[j]) auto it = s.upper_bound(i); if (it != s.end()) { int p = *it; while (p <= limit[i]) { dsu.unite(i, p); p = nxt[p]; } // nxt.update(1, 1, n, L, R, nxt.get(R)); // back.update(1, 1, n, L, R, L); } } } int ans = 1; for (int i = 1; i <= dsu.components; i++) ans = ans * 2 % mod; return ans; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if (fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } cin >> n; for (int i = 1; i <= n; i++) cin >> range[i].fi >> range[i].se; ll ans1 = sub2::solve(); ll ans2 = sub34::solve(); if (ans1 == ans2) cout << ans1; else { // for (int i = 1; i <= n; i++) { // for (int j = i + 1; j <= sub34::limit[i]; j++) { // int k = sub34::nearAffect[j]; // if (k != -1 && k <= sub34::limit[i]) // return cout << 0, 0; // } // } } }

port_facility.cpp: In function 'int main()':
port_facility.cpp:237:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  237 |                 freopen(Task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:238:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |                 freopen(Task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~