Submission #866744

#	Time	Username	Problem	Language	Result	Execution time	Memory
866744		mgl_diamond	Port Facility (JOI17_port_facility)	C++17	22 / 100	6019 ms	12884 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int MOD = 1e9+7;
const int N = 1e6+5;

int n, anc[2*N];
ii cont[N];
set<ii> hold;

int root(int u) {
  return anc[u] < 0 ? u : anc[u] = root(anc[u]);
}

void join(int u, int v) {
  if ((u = root(u)) == (v = root(v))) return;
  if (anc[u] > anc[v]) swap(u, v);
  anc[u] += anc[v];
  anc[v] = u;
}

int main() {
  setIO();
  cin >> n;

  foru(i, 1, n) {
    int l, r;
    cin >> l >> r;
    cont[i] = {l, r};
  }

  foru(i, 1, 2*n) {
    anc[i] = -1;
  }

  sort(cont+1, cont+n+1);

  foru(i, 1, n) {
    int l = cont[i].fi, r = cont[i].se;
    auto lb = hold.lower_bound({l, 0});
    auto rb = hold.lower_bound({r, 0});

    if (lb == hold.end() || lb -> first >= r) {
      hold.insert({r, i});
      continue;
    }

    while (true) {
      join(lb -> second, i + n);
      join(lb -> second + n, i);
      if (lb -> first == prev(rb) -> first) break;
      ++lb;
    }
    
    if (root(i) == root(i+n)) { 
      cout << 0;
      return 0;
    }

    hold.insert({r, i});
  }

  int ans = 1;
  foru(i, 1, n) if (root(i) == i) ans = ans * 2 % MOD;
  cout << ans;
}

Compilation message (stderr)

port_facility.cpp: In function 'void setIO()':
port_facility.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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