Submission #1037085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037085		juicy	Port Facility (JOI17_port_facility)	C++17	100 / 100	1020 ms	167508 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e6 + 5, MD = 1e9 + 7;

int n;
int a[N], b[N], lab[2 * N], c[2 * N];

int get(int u) {
  if (lab[u] < 0) {
    return u;
  }
  int p = get(lab[u]);
  c[u] ^= c[lab[u]];
  lab[u] = p;
  return p;
}

void mrg(int u, int v) {
  int a = get(u), b = get(v);
  int w = c[u] ^ c[v] ^ 1;
  if (a == b) {
    if (w) {
      cout << 0;
      exit(0);
    }
  } else {
    lab[a] += lab[b];
    lab[b] = a;
    c[b] = w;
  }
}

set<array<int, 2>> st;
set<int> cands;

void split(int l, int r, int p) {
  st.erase({l, r});
  auto it = cands.upper_bound(p);
  st.insert({*it, r});
  st.insert({l, *--it});
}

void add(int p) {
  auto it = st.lower_bound({p + 1, 0});
  if (it != st.begin()) {
    --it;
    auto [l, r] = *it;
    if (r >= p) {
      split(l, r, p);
    }
  }
  lab[p] = -1;
  cands.insert(p);
  st.insert({p, p});
}

void add(int l, int r, int u) {
  auto it = st.lower_bound({l, 0});
  if (it != st.begin() && (*prev(it))[1] >= l) {
    --it;
  }
  int L = MD, R = -MD;
  for (; it != st.end() && (*it)[0] <= r; it = st.erase(it)) {
    mrg(u, (*it)[0]);
    L = min(L, (*it)[0]);
    R = max(R, (*it)[1]);
  }
  if (L != MD) {
    st.insert({L, R});
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
  }
  vector<int> ord(n); iota(ord.begin(), ord.end(), 1);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
  for (int u : ord) {
    add(b[u]);
    add(a[u], b[u] - 1, b[u]);
  }
  int res = 1;
  for (int i = 1; i <= 2 * n; ++i) {
    if (lab[i] < 0) {
      res = res * 2 % MD;
    }
  }
  cout << res;
  return 0;
}

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