Submission #497780

#TimeUsernameProblemLanguageResultExecution timeMemory
497780ERHPort Facility (JOI17_port_facility)C++14
100 / 100
918 ms140104 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...