Submission #1227761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227761		abdelhakim	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	3172 ms	9748 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define inf (ll)(1e15) 
#define dbg(x) cerr <<#x << ' ' << x <<endl;
using namespace std;
ll n;
vector<ll> h;
vector<pair<ll,ll>> mn;
vector<ll> ind;
vector<ll> limn;
void init(int N, std::vector<int> H) 
{
  n=N;
  for (int i=0;i<n;i++) h.push_back(H[i]);
  mn.resize(n+1);
  stack<ll> s;
  for (int i=0;i<n;i++)
  {
    while(s.size() && (s.top() < h[i]))
    {
      s.pop();
    }
    if(s.size())
    {
      mn[h[i]].first=s.top();
    }
    s.push(h[i]);
  }
  while(s.size())s.pop();
  for (int i=n-1;i>=0;i--)
  {
    while(s.size() && (s.top() < h[i]))
    {
      s.pop();
    }
    if(s.size())
    {
      mn[h[i]].second=s.top();
    }
    s.push(h[i]);
  }
  ind.resize(n+1);
  for (int i=0;i<n;i++)
  {
    ind[h[i]]=i;
  }
  limn.resize(n);
  for (int i=n-1;i>=0;i--)
  {
    if(mn[h[i]].second!=0)
    {
      limn[h[i]]=1+limn[mn[h[i]].second];
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  ll maxe=0;
  for (int i=A;i<=C;i++)
  {
    maxe=max(h[i],maxe);
  }
  if(maxe!=h[C]) return -1;
  ll cur=h[A];
  ll l3ibat=0;
  ll ans=inf;
  while(cur<h[C])
  {
    ans=min(ans,l3ibat+limn[cur]-limn[h[C]]);
    l3ibat++;
    if(mn[cur].first==0 && mn[cur].second==0)
    {
      break;
    }
    cur=max(mn[cur].first,mn[cur].second);
  }
  return ans;
}

• 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