제출 #1299175

#제출 시각아이디문제언어결과실행 시간메모리
1299175vako_pPort Facility (JOI17_port_facility)C++20
22 / 100
6092 ms3124 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " -----> " << x << endl;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int mxN = 1e6 + 5;
ll n,mod = 1e9 + 7,val[mxN];
pair<ll,ll> a[mxN];

void dfs(ll at){
  for(int i = 0; i < n; i++){
    if((a[i].ff < a[at].ff and a[i].sd > a[at].ff and a[i].sd < a[at].sd)
    or (a[at].ff < a[i].ff and a[at].sd > a[i].ff and a[at].sd < a[i].sd)){
      if(val[i]){
        if(val[at] == val[i]){
          cout << 0;
          exit(0);
        }
        continue;
      }
      val[i] = 3 - val[at];
      dfs(i);
    }
  }
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  cin >> n; 
  for(int i = 0; i < n; i++) cin >> a[i].ff >> a[i].sd;
  sort(a, a + n);
  // for(int i = 0; i < n; i++) s.pb({a[i].sd, i});
  ll ans = 1;
  for(int i = 0; i < n; i++){
    if(val[i]) continue;
    val[i] = 1;
    ans = ans * 2 % mod;
    dfs(i);
  }
  cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...