Submission #1200061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200061		ackhava	Rainforest Jumps (APIO21_jumps)	C++20	In queue	0 ms	0 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define REP(i,o,n) for(int i=o;i<n;i++)
#define fi first
#define se second
#define pb push_back
using namespace std;

vector<int> h;
vector<int> lm;
vector<int> rm;
int n;

void init(int N, std::vector<int> H) {
  h=H;
  n=N;
  vector<pair<int,int>> stck;
  lm.clear(),rm.clear();
  REP(i,0,N){
    while(stck.size() && stck.back().fi < H[i])stck.pop_back();
    lm.pb(-1);
    if(stck.size())lm.back() = (stck.back().se);
    stck.pb({h[i],i});
  }
  stck.clear();
  REP(ix,0,N){
    auto i=N-1-ix;
    while(stck.size() && stck.back().fi < H[i])stck.pop_back();
    rm.pb(-1);
    if(stck.size())rm.back() = (stck.back().se);
    stck.pb({h[i],i});
  }
  reverse(rm.begin(),rm.end());
}

int minimum_jumps(int A, int B, int C, int D) {
  int mx=0;
  REP(i,C,D+1)mx=max(h[i],mx);
  int b=-1;
  int roll=-1;
  REP(ix,A,B+1){
    auto i=A+B-ix;
    roll=max(roll,h[i]);
    if(roll>mx)break;
    if(roll==h[i])b=i;
  }
  // cerr<<"SELECT "<<b<<endl;
  if(b==-1){return -1;}
  roll=b;
  REP(i,1,n+1){
    // cerr<<b<<": "<<lm[b]<<", "<<rm[b]<<endl;
    // if(C <= lm[b] && lm[b] <= D)return i;
    if(C <= rm[b] && rm[b] <= D)return i;
    int lc=-1,rc=-1;
    if(lm[b]!=-1 && h[lm[b]] <= mx)lc=h[lm[b]];
    if(rm[b]!=-1 && h[rm[b]] <= mx)rc=h[rm[b]];
    int prv=b;
    if(lc > rc)b=lm[b];
    else if(rc > lc)b=rm[b];
    else break;
    // assert(h[b]>h[prv]);
  }
  REP(i,A,D+1)if(h[i]>mx)return -1;
  assert(0);
}