Submission #1257877

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

obstacles

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

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;
  }
};

SegmentTreeMax hh_max;
int p[200001];

int GP(int i)
{
  if (i == p[i])
    return i;
  return p[i] = GP(p[i]);
}

void initialize(std::vector<int> T, std::vector<int> H)
{
  hh_max = SegmentTreeMax(H);
  std::vector<std::pair<int, int>> tt;
  tt.push_back(std::make_pair(T[0], T[0]));
  for (int i = 1, min = T[0]; i < T.size(); i++)
  {
    if (T[i] < min)
      min = T[i];
    if (T[i] > tt.back().first)
    {
      if (min == tt.back().second)
      {
        tt.back().first = T[i];
      }
      else
      {
        tt.push_back(std::make_pair(T[i], min));
      }
    }
  }
  for (int i = 0; i < H.size(); i++)
  {
    p[i] = i;
  }
  std::stack<std::pair<int, int>> st;
  for (int i = 0; i < H.size(); i++)
  {
    while (st.size() > 0 && st.top().first > H[i])
    {
      st.pop();
    }
    if (st.size() > 0)
    {
      int j = st.top().second;
      int pi = GP(i);
      int pj = GP(j);
      if (pi != pj)
      {
        int max = hh_max.Query(j, i + 1);
        int l = -1, r = tt.size();
        while (l + 1 < r)
        {
          int m = (l + r) >> 1;
          if (tt[m].first > max)
            r = m;
          else
            l = m;
        }
        if (r < tt.size() && tt[r].second > H[i])
        {
          p[pi] = pj;
        }
      }
    }
    st.push(std::make_pair(H[i], i));
  }
  while (st.size() > 0)
    st.pop();

  for (int i = H.size() - 1; i >= 0; i--)
  {
    while (st.size() > 0 && st.top().first > H[i])
    {
      st.pop();
    }
    if (st.size() > 0)
    {
      int j = st.top().second;
      int pi = GP(i);
      int pj = GP(j);
      if (pi != pj)
      {
        int max = hh_max.Query(i, j + 1);
        int l = -1, r = tt.size();
        while (l + 1 < r)
        {
          int m = (l + r) >> 1;
          if (tt[m].first > max)
            r = m;
          else
            l = m;
        }
        if (r < tt.size() && tt[r].second > H[i])
        {
          p[pi] = pj;
        }
      }
    }
  }
}

bool can_reach(int L, int R, int S, int D)
{
  int s = GP(S);
  int d = GP(D);

  return s == d;
}

• 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