제출 #497780

#제출 시각아이디문제언어결과실행 시간메모리
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...