#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
const int MOD = 1000000007;
int main() {
int N;
cin >> N;
vector<pair<int, int>> intervals(N);
for (int i = 0; i < N; ++i) {
cin >> intervals[i].first >> intervals[i].second;
}
// Контейнеруудыг орж ирэх цагаар эрэмбэлнэ
sort(intervals.begin(), intervals.end());
// Граф үүсгэх
vector<vector<int>> graph(N);
set<pair<int, int>> active; // {гарах цаг, индекс}
for (int i = 0; i < N; ++i) {
int a = intervals[i].first;
int b = intervals[i].second;
// active сетээс давхцаж буй интервалуудыг хайж, ирмэг нэмнэ
auto it = active.lower_bound({a, -1});
for (auto itr = active.begin(); itr != it; ++itr) {
int j = itr->second;
int bj = intervals[j].second;
if (b < bj) {
// Хэсэгчлэн давхцаж, бүрэн агуулаагүй
graph[i].push_back(j);
graph[j].push_back(i);
}
}
active.insert({b, i});
}
// Графыг хоёр өнгөөр будах
vector<int> color(N, -1);
int components = 0;
bool is_bipartite = true;
for (int i = 0; i < N; ++i) {
if (color[i] == -1) {
queue<int> q;
q.push(i);
color[i] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
} else if (color[v] == color[u]) {
is_bipartite = false;
break;
}
}
if (!is_bipartite) break;
}
if (!is_bipartite) break;
components++;
}
}
if (!is_bipartite) {
cout << 0 << endl;
} else {
// Хариу: 2^components модул MOD
long long result = 1;
for (int i = 0; i < components; ++i) {
result = (result * 2) % MOD;
}
cout << result << endl;
}
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... |