Submission #728712

#	Time	Username	Problem	Language	Result	Execution time	Memory
728712		Username4132	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1362 ms	64940 KiB

jumps

#include "jumps.h"
#include<iostream>
#include <vector>
using namespace std;
using pii = pair<int, int>;
#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)
#define F first
#define S second

const int MAXN=200010, LOG=20, INF=1000000000;
int n, arr[MAXN], le[MAXN], ri[MAXN], upl[LOG][MAXN], ups[LOG][MAXN], sho[MAXN], lon[MAXN];
pii sparse[LOG][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]];

  forn(i, n) sparse[0][i]={arr[i], i};
  forn(i, LOG-1) forn(j, n-(1<<i)) sparse[i+1][j]=max(sparse[i][j], sparse[i][j+(1<<i)]);
}

int dist(int A, int C){
  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 : INF;
}


//l < r (strict)
pii query(int l, int r){
  int lg = 8*sizeof(int)-__builtin_clz(r-l)-1;
  pii ret = max(sparse[lg][l], sparse[lg][r-(1<<lg)]);
  return ret;
}

pii getPos(int l, int r, int bound){
  int lo=l-1, hi=r, pos=r;
  while(hi-lo>1){
    int mid=(hi+lo)>>1;
    pii qr = query(mid, r);
    if(qr.F>bound) lo=mid;
    else hi=mid, pos=qr.S;
  }
  return {pos, hi};
}

int minimum_jumps(int A, int B, int C, int D) {
  pii dst = query(C, D+1);
  int pos = getPos(A, B+1, dst.F).F;
  if(pos==B+1) return -1;

  pii mx=query(pos, C);
  int lim=getPos(0, pos, mx.F).S;
  int dis=INF;

  if(mx.F<dst.F) dis = min(dis, dist(pos, mx.S)+1);
  if(lim && arr[lim-1]<dst.F) dis = min(dis, dist(pos, lim-1)+1);
  return dis==INF? -1 : dis;
}

• 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