Submission #798307

#	Time	Username	Problem	Language	Result	Execution time	Memory
798307		Soumya1	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1026 ms	50472 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
const int lg = 20;
int a[mxN], righ[mxN][lg], lef[mxN][lg], best[mxN][lg];
void init(int N, vector<int> H) {
  for (int i = 1; i <= N; i++) a[i] = H[i - 1];
  stack<int> st;
  for (int i = 1; i <= N; i++) {
    while (!st.empty() && a[st.top()] < a[i]) st.pop();
    if (st.empty()) lef[i][0] = i;
    else lef[i][0] = st.top();
    st.push(i);
  }
  while (!st.empty()) st.pop();
  for (int i = N; i >= 1; i--) {
    while (!st.empty() && a[st.top()] < a[i]) st.pop();
    if (st.empty()) righ[i][0] = i;
    else righ[i][0] = st.top();
    st.push(i);
  }
  for (int i = 1; i <= N; i++) {
    if (a[righ[i][0]] > a[lef[i][0]]) best[i][0] = righ[i][0];
    else best[i][0] = lef[i][0];
  }
  for (int j = 1; j < lg; j++) {
    for (int i = 1; i <= N; i++) {
      best[i][j] = best[best[i][j - 1]][j - 1];
      righ[i][j] = righ[righ[i][j - 1]][j - 1];
      lef[i][j] = lef[lef[i][j - 1]][j - 1];
    }
  }
}
int get_max(int l, int r, int v) {
  if (a[r] > v) return -1;
  for (int j = lg - 1; j >= 0; j--) {
    if (lef[r][j] >= l && a[lef[r][j]] < v) r = lef[r][j];
  }
  return r;
}
int minimum_jumps(int A, int B, int C, int D) {
  A++, B++, C++, D++;
  int midx = get_max(C, D, 1e9);
  int start = get_max(A, B, a[midx]);
  if (start == -1) return -1;
  if (B == C - 1) return 1;
  int barrier = a[get_max(B + 1, C - 1, 1e9)];
  if (barrier < a[start]) return 1;
  if (barrier > a[midx]) return -1;
  int ans = 0;
  for (int j = lg - 1;  j >= 0; j--) {
    if (a[best[start][j]] <= barrier) start = best[start][j], ans += (1 << j);
  }
  if (a[start] == barrier) return ans + 1;
  if (a[best[start][0]] < a[midx]) return ans + 2;
  for (int j = lg - 1; j >= 0; j--) {
    if (a[righ[start][j]] <= barrier) start = righ[start][j], ans += (1 << j);
  }
  return ans + 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