Submission #1202009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202009		aykhn	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	493 ms	94032 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;

const int MXN = 2e5 + 5;
const int LOG = 20;

int p[2][LOG][MXN];
int sp[2][LOG][MXN];
vector<int> h;
array<int, 2> mx[LOG][MXN];
int LG[MXN];

int getmx(int l, int r)
{
  if (l > r) return -1;
  int lg = LG[r - l + 1];
  return max(mx[lg][l], mx[lg][r - (1 << lg) + 1])[0];
}

void init(int N, vector<int> H) 
{
  h = H;
  LG[1] = 0;
  for (int i = 2; i < MXN; i++) LG[i] = LG[i >> 1] + 1;
  for (int i = 0; i < N; i++) mx[0][i] = {h[i], i};
  for (int i = 1; i < LOG; i++)
  {
    for (int j = 0; j + (1 << i) - 1 < N; j++)
    {
      mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
    }
  }
  int prv[N], nxt[N];
  {
    vector<int> st;
    for (int i = 0; i < N; i++)
    {
      while (!st.empty() && H[i] > H[st.back()]) st.pop_back();
      if (st.empty()) prv[i] = -1;
      else prv[i] = st.back();
      st.push_back(i);
    }
  }
  {
    vector<int> st;
    for (int i = N - 1; i >= 0; i--)
    {
      while (!st.empty() && H[i] > H[st.back()]) st.pop_back();
      if (st.empty()) nxt[i] = -1;
      else nxt[i] = st.back();
      st.push_back(i);
    }
  }
  for (int i = 0; i < N; i++)
  {
    p[0][0][i] = p[1][0][i] = -1;
    sp[0][0][i] = prv[i], sp[1][0][i] = nxt[i];
    if (nxt[i] != -1 && prv[i] != -1)
    {
      p[0][0][i] = nxt[i], p[1][0][i] = prv[i];
      if (H[nxt[i]] > H[prv[i]]) swap(p[0][0][i], p[1][0][i]);
    }
    else p[0][0][i] = max(nxt[i], prv[i]);
  }
  for (int _ = 0; _ < 2; _++)
  {
    for (int i = 1; i < LOG; i++)
    {
      for (int j = 0; j < N; j++)
      {
        if (p[_][i - 1][j] == -1) 
        {
          p[_][i][j] = -1;
          continue;
        }
        p[_][i][j] = p[_][i - 1][p[_][i - 1][j]];
      }
    }
    for (int i = 1; i < LOG; i++)
    {
      for (int j = 0; j < N; j++)
      {
        if (sp[_][i - 1][j] == -1) 
        {
          sp[_][i][j] = -1;
          continue;
        }
        sp[_][i][j] = sp[_][i - 1][sp[_][i - 1][j]];
      }
    }
  }
}

int dist(int A, int C)
{
  int res = 0;
  for (int _ = 1; _ >= 0 && A != C; _--)
  {
    for (int i = LOG - 1; i >= 0; i--)
    {
      if (p[_][i][A] == -1) continue;
      if (h[p[_][i][A]] >= h[C]) continue;
      A = p[_][i][A];
      res += (1 << i);
    }
    if (p[_][0][A] != -1 && h[p[_][0][A]] <= h[C]) 
    {
      A = p[_][0][A];
      res++;
    }
  }
  if (A != C) return -1;
  return res;
}

int minimum_jumps(int A, int B, int C, int D) 
{
  int a = A, b = B, c = C, d = D;
  int X = C;
  for (int i = LOG - 1; i >= 0; i--)
  {
    if (sp[1][i][X] == -1 || sp[1][i][X] > D) continue;
    X = sp[1][i][X];
  }
  if (h[B] > h[X]) return -1;
  for (int i = LOG - 1; i >= 0; i--)
  {
    if (sp[0][i][B] == -1 || sp[0][i][B] < A) continue;
    if (h[sp[0][i][B]] >= h[X]) continue;
    B = sp[0][i][B];
  }
  if (h[B] > getmx(b + 1, c - 1)) return 1;
  if (getmx(b + 1, c - 1) > h[X]) return -1;
  if (h[C] < getmx(b + 1, c - 1))
  {
    for (int i = LOG - 1; i >= 0; i--)
    {
      if (sp[1][i][C] == -1 || sp[1][i][C] > D) continue;
      if (h[sp[1][i][C]] >= getmx(b + 1, c - 1)) continue;
      C = sp[1][i][C];
    }
    C = sp[1][0][C];
  }
  int res = (dist(B, C) == -1 ? h.size() + 1000 : dist(B, C));
  int cur = B, curres = 0;
  for (int i = LOG - 1; i >= 0; i--)
  {
    if (p[1][i][cur] == -1) continue;
    if (h[p[1][i][cur]] > h[C]) continue;
    cur = p[1][i][cur];
    curres += (1 << i);
  }
  if (p[1][0][cur] != -1 && h[p[1][0][cur]] <= h[X])
  {
    if (c <= p[1][0][cur] && p[1][0][cur] <= d) res = min(curres + 1, res);
    else res = min(curres + 2, res);
  }
  return res;
}

• 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