#include <bits/stdc++.h>
#define int long long
using namespace std;
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int MOD=1e9+7;
void solve() {
int n;cin>>n;
vector<pair<int,int>> vec(n);
vector<bool> dead(n);
vector<int> ev(2*n);
L(i,0,n-1){
cin>>vec[i].first>>vec[i].second;
vec[i].first--;vec[i].second--;
ev[vec[i].first]=i;
ev[vec[i].second]=i;
}
set<pair<int,int>> ativo;
vector<vector<int>> adj(n);
L(i,0,2*n-1){
if(!dead[ev[i]]){
if(!ativo.empty()){
auto pt=ativo.begin();
auto [r,id]=*pt;
if(r<vec[ev[i]].second){
adj[id].push_back(ev[i]);
adj[ev[i]].push_back(id);
}
}
ativo.insert({vec[ev[i]].second,ev[i]});
dead[ev[i]]=1;
}
else{
ativo.erase({i,ev[i]});
}
}
vector<int> cor(n,-1);
auto dfscor=[&](auto&& self, int node, int pai)->void{
cor[node]=cor[pai]^1;
for(auto a:adj[node]){
if(a==pai)continue;
self(self,a,node);
}
};
int cnt=0;
L(i,0,n-1){
if(cor[i]==-1){
cor[i]=1;
cnt++;
dfscor(dfscor,i,i);
}
}
{
vector<vector<int>> st(2);
L(i,0,n-1)dead[i]=0;
L(i,0,2*n-1){
int id=ev[i];
if(dead[id]){
if(st[cor[id]].empty() || st[cor[id]].back()!=id){
cout<<0;return;
}
st[cor[id]].pop_back();
}
else{
dead[id]=1;
st[cor[id]].push_back(id);
}
}
}
int potat=2;
int resp=1;
while(cnt>0){
if(cnt%2)resp*=potat;
cnt/=2;
potat*=potat;
resp%=MOD;
potat%=MOD;
}
cout<<resp;
return;
}
int32_t main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin.exceptions(std::cin.failbit);
int T = 1;
while(T--) {
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... |