This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(vector<bool> v) {
string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
bool fst = 1; string res = "{";
for (const auto& x: v) {
if (!fst) res += ", ";
fst = 0; res += to_string(x);
}
res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 2e6 + 10, MOD = 1e9 + 7;
int n, l[MAXN], r[MAXN], type[MAXN], pw[MAXN], comp;
vector<int> adj[MAXN];
vector<pair<int, int>> ver;
bitset<MAXN> mark, color;
bool bip = 1;
void dfs (int v, int c) {
mark[v] = 1;
color[v] = c;
ver.push_back({l[v], r[v]});
for (int i : adj[v]) {
if (mark[i]) {
bip &= color[i] != c;
}
else {
dfs(i, c ^ 1);
}
}
}
int main() {
ios::sync_with_stdio(0);
#ifndef LOCAL
cin.tie(0);
#endif
pw[0] = 1;
for (int i = 1; i < MAXN; i++) {
pw[i] = 2 * pw[i - 1] >= MOD ? 2 * pw[i - 1] - MOD : 2 * pw[i - 1];
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> l[i] >> r[i];
type[l[i]] = type[r[i]] = i;
}
auto add_edge = [&](int v, int u) {
adj[v].push_back(u);
adj[u].push_back(v);
//wis("add", u, v);
};
set<int> s;
for (int i = 1; i < n + n; i++) {
if (l[type[i]] == i) {
s.insert(i);
}
else {
s.erase(l[type[i]]);
for (auto p = s.lower_bound(l[type[i]]); p != s.end(); p++) {
add_edge(type[i], type[*p]);
}
}
}
for (int i = 0; i < n; i++) {
if (mark[i] == 0) {
comp++;
dfs(i, 0);
vector<int> tmp, stk[2];
for (auto x : ver) {
tmp.push_back(x.first);
tmp.push_back(x.second);
}
ver.clear();
sort(all(tmp));
for (int x : tmp) {
int ind = type[x];
if (l[ind] == x) {
stk[color[ind]].push_back(ind);
}
else {
if (stk[color[ind]].back() != ind) {
cout << 0 << '\n';
return 0;
}
else {
stk[color[ind]].pop_back();
}
}
}
}
}
if (bip == 0) {
cout << 0 << '\n';
return 0;
}
cout << pw[comp] << '\n';
}
# | 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... |