Submission #1257760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257760		ogkostya	Obstacles for a Llama (IOI25_obstacles)	C++20	58 / 100	2096 ms	14516 KiB

obstacles

#include "obstacles.h"
#include <algorithm>
#include <climits>

class SegmentTreeMax
{
  int n;
  std::vector<int> t;

public:
  SegmentTreeMax()
  {
  }

  SegmentTreeMax(const std::vector<int> &a)
  {
    n = a.size();
    t = std::vector<int>(2 * n);
    for (int i = 0; i < n; i++)
      t[i + n] = a[i];

    Build();
  }

  void Build()
  {
    for (int i = n - 1; i > 0; --i)
      t[i] = std::max(t[i << 1], t[i << 1 | 1]);
  }

  void Modify(int p, int value)
  {
    for (t[p += n] = value; p > 1; p >>= 1)
      t[p >> 1] = std::max(t[p], t[p ^ 1]);
  }

  int Query(int l, int r)
  {
    int res = -1;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
      if ((l & 1) == 1)
        res = std::max(res, t[l++]);
      if ((r & 1) == 1)
        res = std::max(res, t[--r]);
    }
    return res;
  }
};

class SegmentTreeMin
{
  int n;
  std::vector<int> t;

public:
  SegmentTreeMin()
  {
  }

  SegmentTreeMin(const std::vector<int> &a)
  {
    n = a.size();
    t = std::vector<int>(2 * n);
    for (int i = 0; i < n; i++)
      t[i + n] = a[i];

    Build();
  }

  void Build()
  {
    for (int i = n - 1; i > 0; --i)
      t[i] = std::min(t[i << 1], t[i << 1 | 1]);
  }

  void Modify(int p, int value)
  {
    for (t[p += n] = value; p > 1; p >>= 1)
      t[p >> 1] = std::min(t[p], t[p ^ 1]);
  }

  int Query(int l, int r)
  {
    int res = INT_MAX;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
      if ((l & 1) == 1)
        res = std::min(res, t[l++]);
      if ((r & 1) == 1)
        res = std::min(res, t[--r]);
    }
    return res;
  }
};

std::vector<int> TT;
std::vector<int> HH;
SegmentTreeMax tt_max;
SegmentTreeMin tt_min;
SegmentTreeMax hh_max;
SegmentTreeMin hh_min;
int N;
int M;

void initialize(std::vector<int> T, std::vector<int> H)
{
  N = T.size();
  M = H.size();
  TT = T;
  HH = H;
  hh_max = SegmentTreeMax(H);
  hh_min = SegmentTreeMin(H);
  tt_max = SegmentTreeMax(T);
  tt_min = SegmentTreeMin(T);
}

int BigLeft(SegmentTreeMax &tr, int i, int value)
{
  int l = -1, r = i + 1;
  while (l + 1 < r)
  {
    int m = (l + r) >> 1;
    if (tr.Query(m, i + 1) > value)
      l = m;
    else
      r = m;
  }
  return l;
}

int BigRight(SegmentTreeMax &tr, int i, int value, int lim)
{
  int l = i, r = lim + 1;
  while (l + 1 < r)
  {
    int m = (l + r) >> 1;
    if (tr.Query(l, m) > value)
      r = m;
    else
      l = m;
  }
  return l;
}

int SmallRight(SegmentTreeMin &tr, int i, int value, int lim)
{
  int l = i, r = lim + 1;
  while (l + 1 < r)
  {
    int m = (l + r) >> 1;
    if (tr.Query(l, m) < value)
      r = m;
    else
      l = m;
  }
  return l;
}

std::vector<int> can_reach(int S)
{
  int i = 0;
  while (true)
  {
    int l = BigLeft(hh_max, S, TT[i] - 1) + 1;
    int r = BigRight(hh_max, S, TT[i] - 1, M) - 1;
    int min = hh_min.Query(l, r + 1);
    int limi = SmallRight(tt_min, i, min + 1, N);
    int max = tt_max.Query(i, limi);
    if (max == TT[i])
      return {max, l, r};
    i = BigRight(tt_max, i, max - 1, N);
  }
}

bool can_reach(int L, int R, int S, int D)
{
  std::vector<int> s_reach = can_reach(S);
  std::vector<int> d_reach = can_reach(D);

  return s_reach[0] == d_reach[0] && s_reach[1] == d_reach[1];
}

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