Submission #1194955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194955		dzuizz	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	471 ms	59952 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5,L=18;
int H[N];
int lf[N][L],rg[N][L],st[N][L],p[N][L];
int n;
void init(int _n,vector<int> _H) {
  n=_n;
  for(int i=0;i<n;++i) H[i]=_H[i];

  for(int i=0;i<n;++i) st[i][0]=i;
  for(int j=0;j<L-1;++j) for(int i=0;i+(1<<(j+1))<=n;++i){
    int a=i,b=i+(1<<j);
    if(H[st[a][j]]>H[st[b][j]]) st[i][j+1]=st[a][j];
    else st[i][j+1]=st[b][j];
  }

  stack<int> s;
  for(int i=0;i<n;++i){
    while(s.size()&&H[s.top()]<=H[i]) s.pop();
    if(s.size()) lf[i][0]=s.top();
    else lf[i][0]=i;
    s.emplace(i);
  }
  while(s.size()) s.pop();
  for(int i=n-1;i>=0;--i){
    while(s.size()&&H[s.top()]<=H[i]) s.pop();
    if(s.size()) rg[i][0]=s.top();
    else rg[i][0]=i;
    s.emplace(i);
  }
  for(int i=0;i<n;++i)
    p[i][0]=H[lf[i][0]]>H[rg[i][0]]?lf[i][0]:rg[i][0];

  for(int j=0;j<L-1;++j) for(int i=0;i<n;++i)
    p[i][j+1]=p[p[i][j]][j],
    lf[i][j+1]=lf[lf[i][j]][j],
    rg[i][j+1]=rg[rg[i][j]][j];
}

int get_min(int l,int r){
  int k=log2(r-l+1);
  return H[st[l][k]]<H[st[r-(1<<k)+1][k]]?st[l][k]:st[r-(1<<k)+1][k];
}

int minimum_jumps(int A,int B,int C,int D){
  int t=C;
  for(int j=L-1;j>=0;--j) if(rg[t][j]<=D)
    t=rg[t][j];

  int s=B;
  for(int j=L-1;j>=0;--j) if(lf[s][j]>=A&&H[lf[s][j]]<H[t])
    s=lf[s][j];

  int x=-1;
  if(B<C-1){
    x=B+1;
    for(int j=L-1;j>=0;--j) if(rg[x][j]<C)
      x=rg[x][j];
    x=H[x];
  }
  //cerr<<s<<" "<<x<<" "<<t<<'\n';
  if(H[s]>=H[t]||x>=H[t]) return -1;


  int ans=0;
  for(int j=L-1;j>=0;--j) if(H[p[s][j]]<x)
    ans+=1<<j,s=p[s][j];
  if(H[s]<x) ++ans;
  return ++ans;
}

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