# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1213895 | VMaksimoski008 | Port Facility (JOI17_port_facility) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ar array
//#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e6 + 5;
ll ans = 1;
int n, col[N], l[N], r[N];
vector<int> g[N];
void dfs(int u, int c) {
col[u] = c;
for(int v : g[u]) {
if(col[v]) {
if(col[v] == c) ans = 0;
continue;
}
dfs(v, 3^c);
}
}
signed main() {
cin >> n;
int cnt = 0;
for(int i=1; i<=n; i++) cin >> l[i] >> r[i];
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(l[i] < l[j] && r[i] < r[j] && l[j] < r[i]) {
cnt++;
g[i].push_back(j);
g[j].push_back(i);
}
}
}
for(int i=1; i<=n; i++) {
if(col[i]) continue;
dfs(i, 1);
ans = ans * 2 % mod;
}
assert(cnt <= 20*n)
cout << ans << '\n';
}