Submission #1255666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255666		flashmt	Obstacles for a Llama (IOI25_obstacles)	C++20	37 / 100	222 ms	32164 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;

template<typename T>
struct SparseTable
{
  int n;
  vector<vector<T>> mat;

  SparseTable(const vector<T>& a)
  {
    n = int(a.size());
    int maxLog = 32 - __builtin_clz(n);
    mat.resize(maxLog);
    mat[0] = a;
    for (int j = 1; j < maxLog; j++)
    {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++)
        mat[j][i] = max(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
    }
  }

  T get(int from, int to)
  {
    if (from > to)
      return -1;
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 31 - __builtin_clz(to - from + 1);
    return max(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int n, m;
vector<int> t, h, l, r;
int isSub2;
SparseTable<int> *st;
set<int> zeroes;

void initialize(vector<int> _t, vector<int> _h) {
  t = _t; h = _h;
  n = size(t); m = size(h);
  isSub2 = 1;
  for (int i = 0; i + 1 < n; i++)
    if (t[i] > t[i + 1])
      isSub2 = 0;

  st = new SparseTable(h);
  l = r = vector<int>(m);

  zeroes.insert(-1);
  zeroes.insert(m);
  for (int i = 0, last = -1; i < m; i++)
  {
    if (h[i] == 0)
      zeroes.insert(i);
    if (h[i] >= 2)
      last = i;
    l[i] = last + 1;
  }
  for (int i = m - 1, last = m; i >= 0; i--)
  {
    if (h[i] >= 2)
      last = i;
    r[i] = last - 1;
  }
}

bool can_reach(int L, int R, int from, int to) {
  if (from > to)
    swap(from, to);

  if (from + 1 == to)
    return 1;

  int maxH = st->get(from, to);

  if (isSub2)
    return maxH < t[n - 1];

  if (t == vector{2, 1, 3})
  {
    if (maxH < 2)
      return 1;

    if (maxH >= 3)
      return 0;

    if (*zeroes.lower_bound(l[from]) > r[from])
      return 0;

    if (*zeroes.lower_bound(l[to]) > r[to])
      return 0;

    return 1;
  }

  return 0;
}

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