Submission #815287

#	Time	Username	Problem	Language	Result	Execution time	Memory
815287		sentheta	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	873 ms	50504 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++;
   
   // top in each intervals [A..B], [B+1..C-1], [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;

   // climb until barrier using skip-edge aka. high-edge
   int ans = 0;
   for (int j = lg - 1;  j >= 0; j--) {
     if (a[best[start][j]] <= barrier) start = best[start][j], ans += (1 << j);
   }
   
   // end up at barrier
   if (a[start] == barrier) return ans + 1;
   // jump over barrier
   if (a[best[start][0]] < a[midx]) return ans + 2;
   // if not jump over, the must move to right to [C..D]
   for (int j = lg - 1; j >= 0; j--) {
     if (righ[start][j] < C) 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