#include <bits/stdc++.h>
using namespace std;
#define int long long int
struct Event {
int time, box_id;
bool is_remove;
const bool operator<(const Event &other) {
return time < other.time;
}
};
const int MAXN = 1'000'001;
const int MOD = 1'000'000'007;
int n;
int A[MAXN], B[MAXN];
vector<Event> events;
int modexp(int a, int p) {
if (p == 0) return 1;
if (p == 1) return a;
int ans = modexp(a, p / 2);
ans %= MOD;
ans *= ans;
ans %= MOD;
if (p % 2 == 1) ans *= a;
ans %= MOD;
return ans % MOD;
}
void solve() {
int ways = 0;
vector<vector<int>> adj(n, vector<int>());
set<pair<int,int>> active;
// for (int i = 0; i < n; i++) {
// for (int j = i+1; j < n; j++) {
// int ci = i, cj = j;
// if (A[ci] > A[cj]) swap(ci, cj);
// if (A[ci] < A[cj] && A[cj] < B[ci] && B[ci] < B[cj]) {
// adj[ci].push_back(cj);
// adj[cj].push_back(ci);
// }
// }
// }
for (auto &E : events) {
int idx = E.box_id;
if (!E.is_remove) {
auto it_lo = active.upper_bound({ A[idx], -1 });
auto it_hi = active.lower_bound({ B[idx], -1 });
vector<pair<int,int>> toLink;
for (auto it = it_lo; it != it_hi; ++it) {
toLink.push_back(*it);
}
for (auto &pr : toLink) {
int other = pr.second;
adj[other].push_back(idx);
adj[idx].push_back(other);
}
active.insert({ B[idx], idx });
} else {
active.erase({ B[idx], idx });
}
}
int cmps = 0; bool bipartite = true;
vector<int> colour(n, -1);
queue<int> q;
for (int i = 0; i < n; i++) {
if (colour[i] != -1 || !bipartite) continue;
cmps++;
q.push(i);
colour[i] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto &el : adj[cur]) {
if (colour[el] == colour[cur]) {
bipartite = false;
break;
} else if (colour[el] == -1) {
colour[el] = colour[cur] == 1 ? 2 : 1;
q.push(el);
}
}
if (!bipartite) break;
}
}
ways = bipartite ? modexp(2, cmps) % MOD : 0;
cout << ways;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i] >> B[i];
}
for (int i = 0; i < n; i++) {
events.push_back(Event {A[i], i, false});
events.push_back(Event {B[i], i, true});
}
sort(events.begin(), events.end());
solve();
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... |