Submission #1194943

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

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5,L=18;
int H[N],lf[N][L],rg[N][L];
int n;
int st[N][L],p[N][L];
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=get_min(A,B),sl=s,sr=s;
  if(H[s]>=H[t]) return -1;
  for(int j=L-1;j>=0;--j) if(lf[sl][j]>=A&&H[lf[sl][j]]<H[t])
    sl=lf[sl][j];
  for(int j=L-1;j>=0;--j) if(rg[sr][j]<=B&&H[rg[sr][j]]<H[t])
    sr=rg[sr][j];
  s=H[sl]>H[sr]?sl:sr;

  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];
  }
  if(x>=H[t]) return -1;

  cerr<<s<<" "<<x<<" "<<t<<'\n';

  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