Submission #981269

#	Time	Username	Problem	Language	Result	Execution time	Memory
981269		Muhammad_Aneeq	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4026 ms	8920 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]={};
bool vis[N]={};
vector<vector<int>>ans;
int ind[N]={};
void init(int N,vector<int> 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);
  }
  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);
      } 
    }
  }
}
int minimum_jumps(int A, int B, int C, int D) 
{
  int minsteps=1e9+10;
  for (int i=A;i<=B;i++)
  {
    int z=i;
    int cnt=0;
    while (ans[ind[z]].back()<C)
    {
      cnt+=ans[ind[z]].size()-(lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),z)-begin(ans[ind[z]]));
      if (nextmx[z]==-1)
      {
        cnt=1e9+10;
        break;
      }
      z=nextmx[z];
    }
    if (nextmx[z]==-1)
      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);
    }
  }
  if (minsteps==1e9+10)
    return -1;  
  return minsteps;
}

• Subtask 1: 0 / 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