Submission #1163288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163288		Malix	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	669 ms	64692 KiB

jumps

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
 
const ll INF=1000000000000000010;
const int inf=1e9+10;
const ll M=1e9+7;

int n,k;
vii x,y,z;

void init(int N, std::vector<int> H) {
  n=N;
  k=log2(n)+1;
  x.resize(n,vi(k,-1)),y.resize(n,vi(k,inf)),z.resize(n,vi(k,inf));
  stack<pi> st;
  st.push({H[0],0});
  REP(i,1,n){
    if(st.top().F<H[i]){
      while(!st.empty()&&st.top().F<H[i]){
        x[st.top().S][0]=i;
        z[st.top().S][0]=i;
        st.pop();
      }
    }
    st.push({H[i],i});
  }
  
  st=stack<pi>();
  st.push({H[n-1],n-1});
  for(int i=n-2;i>=0;i--){
    if(st.top().F<H[i]){
      while(!st.empty()&&st.top().F<H[i]){
        y[st.top().S][0]=i;
        st.pop();
      }
    }
    st.push({H[i],i});
  }
  
  REP(i,0,n){
    if(x[i][0]==-1)x[i][0]=inf;
    if(y[i][0]==inf)y[i][0]=-1;
  }
  REP(j,1,k)REP(i,0,n)if(z[i][j-1]!=inf)z[i][j]=z[z[i][j-1]][j-1];
  REP(j,1,k){
    REP(i,0,n){
      if(x[i][j-1]!=inf)x[i][j]=max(x[i][j],x[x[i][j-1]][j-1]);
      if(y[i][j-1]!=-1)x[i][j]=max(x[i][j],x[y[i][j-1]][j-1]);
      if(x[i][j-1]!=inf)y[i][j]=min(y[i][j],y[x[i][j-1]][j-1]);
      if(y[i][j-1]!=-1)y[i][j]=min(y[i][j],y[y[i][j-1]][j-1]);
    }
    REP(i,0,n){
      if(x[i][j]==-1)x[i][j]=inf;
      if(y[i][j]==inf)y[i][j]=-1;
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  A=B;
  int ans=0,l=A,r=B;
  for(int j=k-1;j>=0;j--){
    if(l!=-1&&x[A][j]>C&&x[B][j]>C)continue;
    if(l==-1&&x[B][j]>C)continue;
    ans+=(1<<j);
    if(l!=-1)A=min(y[l][j],y[r][j]);
    else A=min(A,y[r][j]);
    if(l!=-1){
      if(x[l][j]==inf)B=x[r][j];
      else if(x[r][j]==inf)B=x[l][j];
      else B=max(x[l][j],x[r][j]);
    }
    else B=x[r][j];
    l=A;r=B;
  }
  if(r==C)return ans;
  for(int j=k-1;j>=0;j--){
    if(z[r][j]>C)continue;
    ans+=(1<<j);
    r=z[r][j];
  }
  if(r==C)return ans;
  return -1;
}

• 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