Submission #1177991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177991		Gurban	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	85 ms	49584 KiB

jumps

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

using namespace std;

const int maxn=2e5+5;
const int BB = 20;
int lft[BB][maxn];
int rgt[maxn];
int uly[BB][maxn];
int kici[BB][maxn];

void init(int N, vector<int> H) {
  stack<int>S;
  for(int i = 0;i < N;i++){
    lft[0][i] = -1;
    while(!S.empty() and H[S.top()] < H[i]) S.pop();
    if(!S.empty()) lft[0][i] = S.top();
    S.push(i);
  }
  while(!S.empty()) S.pop();
  for(int i = N-1;i >= 0;i--){
    rgt[i] = N;
    while(!S.empty() and H[S.top()] < H[i]) S.pop();
    if(!S.empty()) rgt[i] = S.top();
    S.push(i);
  }

  for(int i = 0;i < N;i++){
    if(lft[0][i] == -1 and rgt[i] == N){
      uly[0][i] = kici[0][i] = i;
      continue;
    }
    if(lft[0][i] == -1){
      uly[0][i] = kici[0][i] = rgt[i];
    }
    else if(rgt[i] == N){
      uly[0][i] = kici[0][i] = lft[0][i];
    }
    else {
      if(H[lft[0][i]] > H[rgt[i]]){
        uly[0][i] = lft[0][i];
        kici[0][i] = rgt[i];
      }
      else {
        uly[0][i] = rgt[i];
        kici[0][i] = lft[0][i];
      }
    }
  }
  for(int i = 1;i < BB;i++){
    for(int j = 0;j < N;j++){
      lft[i][j] = lft[i-1][lft[i-1][j]];
      uly[i][j] = uly[i-1][uly[i-1][j]];
      kici[i][j] = kici[i-1][kici[i-1][j]];
    }
  }
}


int minimum_jumps(int A, int B, int C, int D) {
  if(rgt[B] > D) return -1;
  int x = B;
  for(int i = BB-1;i >= 0;i--){
    int nxt = lft[i][x];
    if(nxt >= A and rgt[nxt] <= D) x = nxt; 
  }
  // cout<<x<<'\n';
  int ans = 0;
  for(int i = BB-1;i >= 0;i--){
    int nxt = uly[i][x];
    if(rgt[nxt] <= D) x = nxt, ans += (1<<i);
  }
  for(int i = BB-1;i >= 0;i--){
    int nxt = kici[i][x];
    if(rgt[nxt] <= D) x = nxt, ans += (1<<i);
  }
  x = rgt[x];
  ans++;
  if(x >= C and x <= D) 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