Submission #981367

#	Time	Username	Problem	Language	Result	Execution time	Memory
981367		Muhammad_Aneeq	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	4054 ms	12080 KiB

jumps

#include "jumps.h"

#include <vector>
#include <set>
#include <cmath>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int const N=2e5+10,LG=20;
int mx[N][LG]={};
int nextmx[N]={},premx[N]={};
bool vis[N]={};
vector<vector<int>>ans;
int ind[N]={};
bool uni=0;
void init(int N,vector<int> H) 
{
  uni=is_sorted(begin(H),end(H));
  deque<int>d;
  for (int i=0;i<N;i++)
  {
    nextmx[i]=-1;
    if (d.empty())
    {
      d.push_front(i);
      continue;
    }
    while (d.size()&&H[d.front()]<H[i])
    {
      nextmx[d.front()]=i;
      d.pop_front();
    }
    d.push_front(i);
  }
  d={};
  for (int i=N-1;i>=0;i--)
  {
    premx[i]=-1;
    if (d.empty())
    {
      d.push_front(i);
      continue;
    }
    while (d.size()&&H[d.front()]<H[i])
    {
      premx[d.front()]=i;
      d.pop_front();
    }
    d.push_front(i);
  }
  for (int i=0;i<N;i++)
  {
    if (!vis[i])
    {
      int z=i;
      vis[z]=1;
      ans.push_back({z});
      ind[z]=ans.size()-1;
      while (nextmx[z]!=-1&&!vis[nextmx[z]])
      {
        z=nextmx[z];
        vis[z]=1;
        ans.back().push_back(z);
        ind[z]=ans.size()-1;
      } 
    }
  }
}
int minimum_jumps(int A, int B, int C, int D) 
{
  if (uni)
    return C-B;

  int minsteps=1e9+10;
  for (int i=A;i<=B;i++)
  {
    int ex=0;
    int z=i;
    while (z!=-1)
    {
      if (ex>minsteps)
        break;
      int cnt=ex++;
      int prez=z;
      while (ans[ind[z]].back()<C&&z!=-1)
      {
        cnt+=ans[ind[z]].size()-(lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),z)-begin(ans[ind[z]]));
        if (nextmx[ans[ind[z]].back()]==-1)
        {
          cnt=1e9+10;
          break;
        }
        z=nextmx[ans[ind[z]].back()];
      }
      if (z==-1||cnt==1e9+10)
      {
        z=premx[prez];
        continue;
      }
      int f=lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),C)-begin(ans[ind[z]]);
      if (ans[ind[z]][f]<=D)
      {
        int g=lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),z)-begin(ans[ind[z]]);
        cnt+=f-g;
        minsteps=min(cnt,minsteps);
      }
      z=premx[prez];
    }
  }
  if (minsteps==1e9+10)
    return -1;  
  return minsteps;
}

• 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