Submission #414003

#	Time	Username	Problem	Language	Result	Execution time	Memory
414003		flashmt	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1767 ms	56008 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
const int LG = 18;

int n, l[N][LG], r[N][LG], high[N][LG];
vector<int> h;

int isValid(int x)
{
  return x >= 0 && x < n;
}

void initEdges()
{
  vector<pair<int, int>> sortedH;
  for (int i = 0; i < n; i++)
    sortedH.push_back({h[i], i});
  sort(sortedH.begin(), sortedH.end(), greater<pair<int, int>>());
  set<int> s;
  s.insert(-1);
  s.insert(n);
  memset(l, -1, sizeof l);
  memset(r, -1, sizeof r);
  memset(high, -1, sizeof high);
  for (auto [_, i] : sortedH)
  {
    auto it = s.lower_bound(i);
    r[i][0] = *it;
    l[i][0] = *(--it);
    if (!isValid(l[i][0]) && !isValid(r[i][0]));
    else if (!isValid(l[i][0])) high[i][0] = r[i][0];
    else if (!isValid(r[i][0])) high[i][0] = l[i][0];
    else if (h[l[i][0]] > h[r[i][0]]) high[i][0] = l[i][0];
    else high[i][0] = r[i][0];
    s.insert(i);
  }
}

void constructTable()
{
  for (int j = 0; j + 1 < LG; j++)
    for (int i = 0; i < n; i++)
    {
      if (isValid(l[i][j]))
        l[i][j + 1] = l[l[i][j]][j];
      if (isValid(r[i][j]))
        r[i][j + 1] = r[r[i][j]][j];
      if (isValid(high[i][j]))
        high[i][j + 1] = high[high[i][j]][j];
    }
}

void init(int N, vector<int> H) {
  n = N;
  h = H;
  initEdges();
  constructTable();
}

int jump(int &s, int table[N][LG], function<int(int)> cond)
{
  int res = 0;
  for (int i = LG - 1; i >= 0; i--)
  {
    int x = table[s][i];
    if (isValid(x) && cond(x))
    {
      s = x;
      res |= 1 << i;
    }
  }
  return res;
}

int minimum_jumps(int A, int B, int C, int D) {
  int s = B;
  // find where to start
  jump(s, l, [&](int x) {
    return x >= A && isValid(r[x][0]) && r[x][0] <= D;
  });
  // use high edges as most as possible
  int ans = jump(s, high, [&](int x) {
    return isValid(r[x][0]) && r[x][0] < C;
  });
  // check if we need to go 1 more high step
  if (isValid(r[s][0]) && r[s][0] < C)
  {
    int x = high[s][0];
    if (isValid(x) && isValid(r[x][0]) && r[x][0] <= D)
    {
      s = x;
      ans++;
    }
  }
  // just go right
  ans += jump(s, r, [&](int x) {
    return x < C;
  });
  return r[s][0] >= C && r[s][0] <= D ? ans + 1 : -1;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19