Submission #1257652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257652		ogkostya	Obstacles for a Llama (IOI25_obstacles)	C++20	24 / 100	93 ms	9800 KiB

obstacles

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

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

public:
  SegmentTree()
  {
  }

  SegmentTree(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 = 0;
    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;
  }
};

std::vector<int> TT;
std::vector<int> HH;
SegmentTree tr;

void initialize(std::vector<int> T, std::vector<int> H)
{
  TT = T;
  HH = H;
  tr = SegmentTree(H);
}

bool can_reach(int L, int R, int S, int D)
{
  if (S > D)
    std::swap(S, D);

  return TT[TT.size() - 1] > tr.Query(S, D + 1);
}

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