Submission #1178024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178024		Gurban	Rainforest Jumps (APIO21_jumps)	C++20	44 / 100	622 ms	65404 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[BB][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] = N;
    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[0][i] = N;
    while(!S.empty() and H[S.top()] < H[i]) S.pop();
    if(!S.empty()) rgt[0][i] = S.top();
    S.push(i);
  }

  for(int i = 0;i < N;i++){
    if(lft[0][i] == N and rgt[0][i] == N){
      uly[0][i] = kici[0][i] = i;
      continue;
    }
    if(lft[0][i] == N){
      uly[0][i] = kici[0][i] = rgt[0][i];
    }
    else if(rgt[0][i] == N){
      uly[0][i] = kici[0][i] = lft[0][i];
    }
    else {
      if(H[lft[0][i]] > H[rgt[0][i]]){
        uly[0][i] = lft[0][i];
        kici[0][i] = rgt[0][i];
      }
      else {
        uly[0][i] = rgt[0][i];
        kici[0][i] = lft[0][i];
      }
    }
  }
  for(int i = 0;i < BB;i++) lft[i][N] = rgt[i][N] = N;
  for(int i = 1;i < BB;i++){
    for(int j = 0;j < N;j++){
      lft[i][j] = lft[i-1][lft[i-1][j]];
      rgt[i][j] = rgt[i-1][rgt[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[0][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[0][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[0][nxt] <= D) x = nxt, ans += (1<<i);
    if(x >= C) return ans;
  }
  // cout<<x<<'\n';
  for(int i = BB-1;i >= 0;i--){
    int nxt = rgt[i][x];
    if(nxt < C) x = nxt, ans += (1<<i);
  }
  x = rgt[0][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: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 0 / 19