Submission #1201825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201825		aykhn	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4046 ms	16072 KiB

jumps

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

using namespace std;

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

int n;
vector<int> h;
vector<int> adj[MXN];

void init(int N, vector<int> H) 
{
  n = N, h = H;
  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++)
  {
    for (int j : {nxt[i], prv[i]})
    {
      if (j != -1) adj[i].push_back(j);
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) 
{
  // A = max(A, B), C = min(C, D);
  vector<int> d(n, -1);
  queue<int> q;
  for (int i = A; i <= B; i++) d[i] = 0, q.push(i);
  while (!q.empty())
  {
    int a = q.front();
    q.pop();
    if (C <= a && a <= D) return d[a];
    for (int &v : adj[a])
    {
      if (d[v] == -1)
      {
        d[v] = d[a] + 1;
        q.push(v);
      }
    }
  }
  return -1;
}

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