Submission #643747

#	Time	Username	Problem	Language	Result	Execution time	Memory
643747		colossal_pepe	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	1207 ms	33332 KiB

jumps

#include "jumps.h"
 
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
 
const int INF = 1e9;
 
int n, k;
vector<int> h, idx;
vector<vector<int>> st_max, st_nxt;
 
void init(int N, vector<int> H) {
  n = N;
  h = H;
  k = __lg(n) + 1;
  idx.resize(n);
  for (int i = 0; i < n; i++) {
    h[i]--;
    idx[h[i]] = i;
  }
  st_max.resize(k, vector<int>(n));
  stack<int> s;
  for (int i = 0; i < n; i++) {
    while (not s.empty() and s.top() <= h[i]) s.pop();
    st_max[0][i] = s.empty() ? h[i] : s.top();
    s.push(h[i]);
  }
  while (not s.empty()) s.pop();
  st_nxt.resize(k, vector<int>(n));
  for (int i = n - 1; i >= 0; i--) {
    while (not s.empty() and s.top() <= h[i]) s.pop();
    st_max[0][i] = max(st_max[0][i], s.empty() ? h[i] : s.top());
    st_nxt[0][i] = s.empty() ? h[i] : s.top();
    s.push(h[i]);
  }
  for (int i = 1; i < k; i++) {
    for (int j = 0; j < n; j++) {
      st_max[i][j] = st_max[i - 1][idx[st_max[i - 1][j]]];
      st_nxt[i][j] = st_nxt[i - 1][idx[st_nxt[i - 1][j]]];
    }
  }
}
 
int minimum_jumps(int a, int b, int c, int d) {
  int ans = 0;
  for (int bit = k - 1; bit >= 0; bit--) {
    if (st_max[bit][a] < h[d]) {
      ans += (1 << bit);
      a = idx[st_max[bit][a]];
    }
  }
  for (int bit = k - 1; bit >= 0; bit--) {
    if (st_nxt[bit][a] < h[d]) {
      ans += (1 << bit);
      a = idx[st_nxt[bit][a]];
    }
  }
  return (st_nxt[0][a] == h[d] ? ans + 1 : -1);
}

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