Submission #1272834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272834		rxlfd314	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	185 ms	78228 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 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;
ari2 lift_left[mxN][LOG+1], lift_right[mxN][LOG+1];

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<int> L(M), R(M), stk;
  FOR(i, 0, M-1) {
    while (size(stk) && H[stk.back()] > H[i])
      stk.pop_back();
    L[i] = size(stk) ? stk.back() : -1;
    stk.push_back(i);
  }
  stk.clear();
  ROF(i, M-1, 0) {
    while (size(stk) && H[stk.back()] > H[i])
      stk.pop_back();
    R[i] = size(stk) ? stk.back() : -1;
    stk.push_back(i);
  }

  st.init(H);
  vt<int> ord(M);
  iota(all(ord), 0);
  sort(all(ord), [&](const int &a, const int &b) { return H[a] < H[b]; });
  for (const auto &i : ord) {
    const auto check = [&](const int j) {
      if (j < 0)
        return false;
      int lo = 0, hi = N;
      while (lo < hi) {
        const int mid = lo + hi >> 1;
        if (pmax[mid] > st.query(min(i, j), max(i, j)))
          hi = mid;
        else
          lo = mid + 1;
      }
      return lo < N && pmin[lo] > H[i];
    };
    lift_left[i][0] = {check(L[i]) ? L[i] : i, i};
    lift_right[i][0] = {check(R[i]) ? R[i] : i, i};
    if (L[i] < 0 || R[i] < 0)
      continue;
    if (H[L[i]] >= H[R[i]] && check(L[i]))
      lift_right[i][0] = max(lift_right[i][0], lift_right[L[i]][0]);
    if (H[L[i]] <= H[R[i]] && check(R[i]))
      lift_left[i][0] = min(lift_left[i][0], lift_left[R[i]][0]);
  }

  FOR(j, 1, LOG)
    FOR(i, 0, M-1) {
      lift_left[i][j][0] = lift_left[lift_left[i][j-1][0]][j-1][0];
      lift_left[i][j][1] = max(lift_left[i][j-1][1], lift_left[lift_left[i][j-1][0]][j-1][1]);
      lift_right[i][j][0] = lift_right[lift_right[i][j-1][0]][j-1][0];
      lift_right[i][j][1] = min(lift_right[i][j-1][1], lift_right[lift_right[i][j-1][0]][j-1][1]);
    }
}

bool can_reach(int L, int R, int S, int D) {
  const auto good = [&](const int x) { return L <= x && x <= R; };
  const auto el = [&](int i) {
    ROF(j, LOG, 0)
      if (good(lift_left[i][j][0]) && good(lift_left[i][j][1]))
        i = lift_left[i][j][0];
    return i;
  };
  const auto er = [&](int i) {
    ROF(j, LOG, 0)
      if (good(lift_right[i][j][0]) && good(lift_right[i][j][1]))
        i = lift_right[i][j][0];
    return i;
  };
  vt<int> a = {el(S), er(S)}, b = {el(D), er(D)};
  FOR(i, 0, 1)
    FOR(j, 0, 1)
      if (a[i] == b[j])
        return true;
  return false;
}

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