#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
ll modexp(ll a, ll p) {
if (p == 0) return 1;
if (p == 1) return a;
ll 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 = 1;
vector<vector<int>> crossings(n, vector<int>()); // had this idea previously to precompute crossings js was trying to brute force first
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int ci = i, cj = j;
if (A[cj] < A[ci]) swap(ci, cj);
if (!(A[ci] < A[cj] && A[cj] < B[ci] && B[ci] < B[cj])) continue;
crossings[ci].push_back(cj);
crossings[cj].push_back(ci);
}
}
vector<int> group(n, -1);
int cmps = 0;
// push the constraints down the group (ie. each incompatible thing on a different side)
for (int i = 0; i < n; i++) {
if (group[i] != -1) continue;
group[i] = 1;
cmps++;
queue<int> q;
q.push(i);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto &restriction : crossings[cur]) {
if (group[restriction] == -1) {
group[restriction] = group[cur] == 1 ? 2 : 1; // push down the constraint
q.push(restriction);
} else if (group[restriction] == group[cur]) { // inconsistency, need to break
cout << 0;
return;
}
}
}
}
ways = modexp(2, cmps); // either group 1 in A g2 B or g1 B g2 A so 2 ways for each cmp
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... |