Submission #1299175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299175		vako_p	Port Facility (JOI17_port_facility)	C++20	22 / 100	6092 ms	3124 KiB

port_facility

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22