Submission #1256342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256342		flashmt	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	100 ms	26304 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]);
  }
};

struct DisjointSet
{
  int n;
  vector<int> ds, h;

  DisjointSet(int n, vector<int> &h): n(n), h(h)
  {
    ds = vector<int>(n);
    for (int i = 0; i < n; i++)
      ds[i] = i;
  }

  int get(int x)
  {
    return x == ds[x] ? x : ds[x] = get(ds[x]);
  }

  int join(int x, int y)
  {
    int dx = get(x), dy = get(y);
    if (dx == dy)
      return 0;
    if (h[dx] > h[dy])
      swap(dx, dy);
    ds[dy] = dx;
    return 1;
  }
};

int n, m;
vector<int> t, h;
vector<int> minT, maxT, maxTForCol;
SparseTable<int> *table;

void initialize(vector<int> _t, vector<int> _h) {
  t = _t; h = _h;
  n = size(t); m = size(h);
  table = new SparseTable(h);
  minT = maxT = vector<int>(n);
  for (int i = 0; i < n; i++)
  {
    minT[i] = i ? min(minT[i - 1], t[i]) : t[i];
    maxT[i] = i ? max(maxT[i - 1], t[i]) : t[i];
  }

  vector<int> maxRow(m, -1);
  for (int i = 0; i < m; i++)
  {
    int low = 0, high = n - 1;
    while (low <= high)
    {
      int mid = (low + high) / 2;
      if (minT[mid] > h[i])
      {
        maxRow[i] = mid;
        low = mid + 1;
      }
      else high = mid - 1;
    }
  }

  DisjointSet ds(m, h);

  vector<int> st;
  for (int i = 0; i < m; i++)
  {
    while (!empty(st) && h[st.back()] >= h[i])
      st.pop_back();
    if (!empty(st))
    {
      int j = st.back();
      int row = min(maxRow[i], maxRow[j]);
      int maxHBetween = table->get(j + 1, i - 1);
      if (row >= 0 && maxT[row] > maxHBetween)
        ds.join(i, j);
    }
    st.push_back(i);
  }

  st.clear();
  for (int i = m - 1; i >= 0; i--)
  {
    while (!empty(st) && h[st.back()] >= h[i])
      st.pop_back();
    if (!empty(st))
    {
      int j = st.back();
      int row = min(maxRow[i], maxRow[j]);
      int maxHBetween = table->get(i + 1, j - 1);
      if (row >= 0 && maxT[row] > maxHBetween)
        ds.join(i, j);
    }
    st.push_back(i);
  }

  maxTForCol.assign(m, 0);
  for (int i = 0; i < m; i++)
  {
    int lowestCol = ds.get(i);
    maxTForCol[i] = maxT[maxRow[lowestCol]];
  }
}

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 = table->get(from, to);
  return min(maxTForCol[from], maxTForCol[to]) > maxH;
}

• 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