제출 #1272775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272775		rxlfd314	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	239 ms	45544 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 200005, LOG = 17;

struct DSU {
  int uf[mxN];
  void init() { memset(uf, -1, sizeof(uf)); }
  int find(const int i) { return uf[i] < 0 ? i : uf[i] = find(uf[i]); }
  bool unite(int a, int b) {
    if ((a = find(a)) == (b = find(b)))
      return false;
    if (uf[a] > uf[b])
      swap(a, b);
    uf[a] += uf[b];
    uf[b] = a;
    return true;
  }
} uf;

struct ST {
  int st[mxN][LOG+1];
  void init(const vt<int> &A) {
    const int N = size(A);
    FOR(i, 0, N-1)
      st[i][0] = A[i];
    FOR(j, 1, LOG)
      FOR(i, 0, N-(1<<j))
        st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]);
  }
  int query(const int l, const int r) {
    const int n = 31 - __builtin_clz(r-l+1);
    return max(st[l][n], st[r-(1<<n)+1][n]);
  }
} st;

int N, M;

void initialize(const vt<int> T, const vt<int> H) {
  N = size(T), M = size(H);
  
  vt<int> pmin = T, pmax = T;
  FOR(i, 1, N-1) {
    pmin[i] = min(pmin[i-1], T[i]);
    pmax[i] = max(pmax[i-1], T[i]);
  }
  vt<vt<int>> rem(N+1);
  FOR(i, 0, M-1) {
    int lo = 0, hi = N;
    while (lo < hi) {
      const int mid = lo + hi >> 1;
      if (pmin[mid] > H[i])
        lo = mid + 1;
      else
        hi = mid;
    }
    rem[lo].push_back(i);
  }
  
  vt<vt<int>> join(N+1);
  st.init(H);
  FOR(i, 0, M-2) {
    int lo = 0, hi = N;
    while (lo < hi) {
      const int mid = lo + hi >> 1;
      if (pmax[mid] > max(H[i], H[i+1]))
        hi = mid;
      else
        lo = mid + 1;
    }
    join[lo].push_back(i);
  }
  
  set<int> active;
  FOR(i, 0, M-1)
    active.insert(i);
  uf.init();
  FOR(x, 0, N-1) {
    for (const auto &i : rem[x])
      if (active.count(i))
        active.erase(active.find(i));
    for (const auto &i : join[x]) {
      const auto it = active.upper_bound(i);
      if (it == active.end() || it == active.begin())
        continue;
      const int j = *prev(it), k = *it;
      if (T[x] > st.query(j, k)) {
        uf.unite(j, k);
        active.erase(active.find(H[j] < H[k] ? k : j));
      }
    }
  }
}

bool can_reach(int L, int R, int S, int D) {
  return uf.find(S) == uf.find(D);
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 21 / 21
• Subtask 5: 25 / 25
• Subtask 6: 0 / 17