Submission #530695

#	Time	Username	Problem	Language	Result	Execution time	Memory
530695		czhang2718	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1408 ms	59968 KiB

jumps

#include "jumps.h"
// #include <bits/stdc++.h>
#include <vector>
#include <cassert>
using namespace std;

#define rep(i,a,b) for(int i=a; i<=b; i++)
#define f first
#define s second

const int N=200001, LG=18;

int lg[N];
int go[N][LG], goleft[N][LG], goright[N][LG];
int mx[N][LG];
int pos[N];
int n;
int h[N];

int get_max(int l, int r){
  if(r<l) return 0;
  int len=lg[r-l+1];
  return max(mx[l][len], mx[r-(1<<len)+1][len]);
}

void init(int nn, std::vector<int> H) {
  n=nn;
  rep(i,2,n){
    lg[i]=lg[i/2]+1;
  }
  rep(i,0,n-1){
    mx[i][0]=H[i];
    pos[H[i]]=i;
  }
  rep(j,1,lg[n]){
    rep(i,0,n-(1<<j)){
      mx[i][j]=max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
    }
  }
  rep(i,0,n-1){
    int ind=i;
    for(int j=lg[n]; j>=0; j--){
      if(ind-(1<<j)>=0 && get_max(ind-(1<<j), i)==H[i]) ind-=(1<<j);
    }
    goleft[i][0]=(ind==0?-1:H[ind-1]);
  }
  rep(i,0,n-1){
    int ind=i;
    for(int j=lg[n]; j>=0; j--){
      if(ind+(1<<j)<n && get_max(i, ind+(1<<j))==H[i]) ind+=(1<<j);
    }
    goright[i][0]=(ind==n-1?-1:H[ind+1]);
  }
  rep(i,0,n-1){
    go[i][0]=max(goleft[i][0], goright[i][0]);
  }
  rep(j,1,lg[n]){
    rep(i,0,n-1){
      goright[i][j]=(goright[i][j-1]==-1?-1:goright[pos[goright[i][j-1]]][j-1]);
      go[i][j]=(go[i][j-1]==-1?-1:go[pos[go[i][j-1]]][j-1]);
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  int mx=get_max(C, D);
  if(get_max(B, C)>mx) return -1;

  for(int j=lg[n]; j>=0; j--){
    if(A+(1<<j)<=B && get_max(A+(1<<j), B)>mx) A+=(1<<j);
  }
  if(get_max(A, B)>mx) A++;

  int ans=0;
  int a=pos[get_max(A, B)];
  int y=get_max(B+1, C-1);
  for(int j=lg[n]; j>=0; j--){
    if(go[a][j]>0 && go[a][j]<=y) ans+=(1<<j), a=pos[go[a][j]];
  }
  if(goright[a][0]!=-1 && pos[goright[a][0]]>=C) return ans+1;
  if(goleft[a][0]!=-1 && goleft[a][0]<mx && goleft[a][0]>y) return ans+2;
  for(int j=lg[n]; j>=0; j--){
    if(goright[a][j]>0 && pos[goright[a][j]]<C) ans+=(1<<j), a=pos[goright[a][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