This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
using namespace std;
vector<int> temp[1000001], color(1000001, -1);
int a[1000001], b[1000001];
bool continuar=0;
void recursion(int u){
for(int v:temp[u]){
if(color[v]==!color[u]){
continue;
} else {
if(color[v]==color[u]){
continuar=1;
cout<<0;
break;
} else {
color[v]=!color[u];
recursion(v);
if(continuar){
break;
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cout.tie();
cin.tie();
int n, z=0;
cin>>n;
int tiempo[1+2*n];
for(int i=1; i<=n; i++){
cin>>a[i]>>b[i];
tiempo[a[i]]=i;
tiempo[b[i]]=-i;
}
vector<int> lista, t[2];
for(int e=1; e<=2*n; e++){
if(tiempo[e]>0){
continue;
}
while(!lista.empty() && a[-tiempo[e]]<a[lista.back()]){
lista.pop_back();
}
if(!lista.empty() && a[-tiempo[e]] < b[lista.back()]){
temp[-tiempo[e]].push_back(lista.back());
temp[lista.back()].push_back(-tiempo[e]);
}
lista.push_back(-tiempo[e]);
}
lista.clear();
for(int e=2*n; e>=1; e--){
if(tiempo[e]<0){
continue;
}
while(!lista.empty() && b[lista.back()]<b[tiempo[e]]){
lista.pop_back();
}
if(!lista.empty() && a[lista.back()]<b[tiempo[e]]){
temp[tiempo[e]].push_back(lista.back());
temp[lista.back()].push_back(tiempo[e]);
}
lista.push_back(tiempo[e]);
}
for(int i=1; i<=n; i++){
if(color[i]!=-1){
continue;
}
z++;
color[i]=0;
recursion(i);
if(continuar){
return 0;
}
}
for(int e=1; e<=2*n; e++){
if(tiempo[e]>0){
t[color[tiempo[e]]].push_back(tiempo[e]);
} else {
if(t[color[-tiempo[e]]].back()==-tiempo[e]){
t[color[-tiempo[e]]].pop_back();
} else {
cout<<0;
return 0;
}
}
}
int total=1;
for(int x=1; x<=z; x++){
total=(2*total)%1000000007;
}
cout<<total<<'\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... |