Submission #728639

#	Time	Username	Problem	Language	Result	Execution time	Memory
728639		Username4132	Rainforest Jumps (APIO21_jumps)	C++14	23 / 100	1286 ms	37068 KiB

jumps

#include "jumps.h"
#include<iostream>
#include <vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)

const int MAXN=200010, LOG=20;
int n, arr[MAXN], le[MAXN], ri[MAXN], upl[LOG][MAXN], ups[LOG][MAXN], sho[MAXN], lon[MAXN];

void init(int N, vector<int> H) {
  n=N;
  forn(i, n) arr[i]=H[i]-1;
  le[0]=-1;
  ri[n-1]=n;
  forn(i, n-1){
    int cur=i;
    while(cur!=-1 && arr[cur]<arr[i+1]) cur=le[cur];
    le[i+1]=cur;
  }
  dforn(i, n-1){
    int cur=i+1;
    while(cur!=n && arr[cur]<arr[i]) cur=ri[cur];
    ri[i]=cur;
  }
  arr[n]=sho[n]=lon[n]=n;
  forn(i, n){
    if(arr[i]==n-1) sho[i]=lon[i]=n;
    else{
      int a=le[i], b=ri[i];
      if(a==-1) lon[i]=sho[i]=b;
      else if(b==n) lon[i]=sho[i]=a;
      else if(arr[a]>arr[b]) lon[i]=a, sho[i]=b;
      else lon[i]=b, sho[i]=a;
    }
  }
  forn(i, n+1) upl[0][i]=lon[i], ups[0][i]=sho[i];
  forn(i, LOG-1) forn(j, n+1) upl[i+1][j]=upl[i][upl[i][j]];
  forn(i, LOG-1) forn(j, n+1) ups[i+1][j]=ups[i][ups[i][j]];
}

int minimum_jumps(int A, int B, int C, int D) {
  int cur=A, ans=0;
  dforn(i, LOG) if(arr[upl[i][cur]]<=arr[C]) cur=upl[i][cur], ans+=(1<<i);
  dforn(i, LOG) if(arr[ups[i][cur]]<=arr[C]) cur=ups[i][cur], ans+=(1<<i);
  return cur==C? ans : -1;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19