Submission #1238700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238700		Joon_Yorigami	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	589 ms	97508 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
using ll = long long;
using vll = vector<long long>;
constexpr ll inf = LONG_LONG_MAX;
constexpr ll max_n = 200005;
constexpr ll max_log = 20;
vector<vll> l;
vector<vll> r;
vector<vll> greedy;

void init(int n,vector<int> h)
{
  h.push_back(-1);
  vector<vll>(max_log,vll(max_n,n)).swap(l);
  vector<vll>(max_log,vll(max_n,n)).swap(r);
  vector<vll>(max_log,vll(max_n,n)).swap(greedy);
  stack<int> s;
  for(int i=0;i<n;i++)
  {
    while(!s.empty()&&h[s.top()]<h[i])
      s.pop();
    if(!s.empty())
      l[0][i]=s.top();
    s.push(i);
  }
  stack<int>().swap(s);
  for(int i=n-1;i>=0;i--)
  {
    while(!s.empty()&&h[s.top()]<h[i])
      s.pop();
    if(!s.empty())
      r[0][i]=s.top();
    s.push(i);
  }
  for(int i=0;i<n;i++)
  {
    if(h[l[0][i]]>h[r[0][i]])
      greedy[0][i]=l[0][i];
    else
      greedy[0][i]=r[0][i];
  }
  for(int i=1;i<max_log;i++)
  {
    for(int j=0;j<n;j++)
    {
      l[i][j]=l[i-1][l[i-1][j]];
      r[i][j]=r[i-1][r[i-1][j]];
      greedy[i][j]=greedy[i-1][greedy[i-1][j]];
    }
  }
}

int minimum_jumps(int a, int b, int c, int d)
{
  int ans=0;
  for(int i=max_log-1;i>=0;i--)
    if(l[i][b]>=a&&r[0][l[i][b]]<=d)
      b=l[i][b];
  if(c<=r[0][b]&&r[0][b]<=d)
    return 1;
  for(int i=max_log-1;i>=0;i--)
  {
    if(r[0][greedy[i][b]]<c)
    {
      ans+=(1ll<<i);
      b=greedy[i][b];
    }
  }
  if(r[0][greedy[0][b]]<=d)
    return ans+2;
  for(int i=max_log-1;i>=0;i--)
  {
    if(r[i][b]<c)
    {
      ans+=(1ll<<i);
      b=r[i][b];
    }
  }
  if (r[0][b]<c||r[0][b]>d) return -1;
  else return ans+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