Submission #569152

#	Time	Username	Problem	Language	Result	Execution time	Memory
569152		Soumya1	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	1 ms	464 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
const int lg = 20;
int l[lg][mxN], r[lg][mxN];
int h[mxN];
void init(int n, vector<int> H) {
  stack<int> s;
  for (int i = 0; i < n; i++) h[i + 1] = H[i];
  for (int i = 1; i <= n; i++) {
    while (!s.empty() && h[s.top()] <= h[i]) s.pop();
    l[0][i] = (s.empty() ? 0 : s.top());
    s.push(i);
  }
  while (!s.empty()) s.pop();
  for (int i = n; i >= 1; i--) {
    while (!s.empty() && h[s.top()] <= h[i]) s.pop();
    r[0][i] = (s.empty() ? 0 : s.top());
    s.push(i);
  }
  for (int i = 1; i <= n; i++) {
    if (h[l[0][i]] > h[r[0][i]]) swap(l[0][i], r[0][i]);
  }
  h[0] = 1e9;
  for (int j = 1; j < lg; j++) {
    for (int i = 1; i <= n; i++) {
      l[j][i] = l[j - 1][l[j - 1][i]];
      r[j][i] = r[j - 1][r[j - 1][i]];
    }
  }
}
int minimum_jumps(int a, int b, int c, int d) {
  int ans = 0;
  for (int j = lg - 1; j >= 0; j--) {
    if (h[r[j][a]] <= h[c]) {
      a = r[j][a];
      ans += (1 << j);
    }
  }
  for (int j = lg - 1; j >= 0; j--) {
    if (h[l[j][a]] <= h[c]) {
      a = l[j][a];
      ans += (1 << j);
    }
  }
  if (a == c) return ans;
  return -1;
}

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