Submission #1144727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144727		byunjaewoo	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	630 ms	139668 KiB

jumps

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

const int N=200010, L=20;
int n, a[N], nxt1[L][N], nxt2[L][N];
pair<int, int> mxl[L][N], mxr[L][N], mnl[L][N], mnr[L][N];
vector<int> stk;

void init(int N, vector<int> H) {
  n=N;
  for(int i=1; i<=n; i++) a[i]=H[i-1];
  for(int i=1; i<=n; i++) mxl[0][i]=mxr[0][i]=mnl[0][i]=mnr[0][i]={a[i], i};
  for(int i=1; i<L; i++) {
    for(int j=1; j<=n; j++) {
      if(j+(1<<i)-1<=n) {
        mxl[i][j]=max(mxl[i-1][j], mxl[i-1][j+(1<<(i-1))]);
        mnl[i][j]=min(mnl[i-1][j], mnl[i-1][j+(1<<(i-1))]);
      }
      if(j-(1<<i)+1>=1) {
        mxr[i][j]=max(mxr[i-1][j], mxr[i-1][j-(1<<(i-1))]);
        mnr[i][j]=min(mnr[i-1][j], mnr[i-1][j-(1<<(i-1))]);
      }
    }
  }
  for(int i=n; i>=1; i--) {
    while(!stk.empty() && a[stk.back()]<=a[i]) stk.pop_back();
    if(!stk.empty()) nxt1[0][i]=nxt2[0][i]=stk.back();
    stk.push_back(i);
  }
  stk.clear();
  for(int i=1; i<=n; i++) {
    while(!stk.empty() && a[stk.back()]<=a[i]) stk.pop_back();
    if(!stk.empty() && a[nxt1[0][i]]<a[stk.back()]) nxt1[0][i]=stk.back();
    stk.push_back(i);
  }
  for(int i=1; i<L; i++) for(int j=1; j<=n; j++) {
    nxt1[i][j]=nxt1[i-1][nxt1[i-1][j]], nxt2[i][j]=nxt2[i-1][nxt2[i-1][j]];
  }
}

pair<int, int> querymn(int l, int r) {
  int tmp=31-__builtin_clz(r-l+1);
  return min(mnl[tmp][l], mnr[tmp][r]);
}

pair<int, int> querymx(int l, int r) {
  if(l>r) return {0, 0};
  int tmp=31-__builtin_clz(r-l+1);
  return max(mxl[tmp][l], mxr[tmp][r]);
}

int queryp(int l, int r, int x) {
  int p=r;
  for(int i=L-1; i>=0; i--) if(mxr[i][p-1].first && mxr[i][p-1].first<x) p-=(1<<i);
  return max(l, p);
}

int queryq(int l, int r, int x) {
  for(int i=L-1; i>=0; i--) if(mxl[i][l].first && mxl[i][l].first<=x) l+=(1<<i);
  return min(r, l);
}

int query(int l, int lo, int hi) {
  if(a[l]>=lo && a[l]<hi) return 0;
  int ret=0;
  for(int i=L-1; i>=0; i--) if(nxt1[i][l] && a[nxt1[i][l]]<lo) ret+=(1<<i), l=nxt1[i][l];
  if(a[nxt1[0][l]]<hi) return ret+1;
  for(int i=L-1; i>=0; i--) if(nxt2[i][l] && a[nxt2[i][l]]<lo) ret+=(1<<i), l=nxt2[i][l];
  return ret+1;
}

int minimum_jumps(int A, int B, int C, int D) {
  A++, B++, C++, D++;
  pair<int, int> x=querymx(B+1, C-1), mx2=querymx(C, D);
  if(a[B]>=mx2.first || (B+1<C && x.first>=mx2.first)) return -1;
  A=queryp(A, B, mx2.first);
  pair<int, int> mx1=querymx(A, B);
  if(x.second) return query(mx1.second, x.first, mx2.first)+1;
  return query(mx1.second, 0, mx2.first)+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