Submission #728249

#	Time	Username	Problem	Language	Result	Execution time	Memory
728249		Md_Abdullah	Rainforest Jumps (APIO21_jumps)	C++17	8 / 100	4086 ms	20480 KiB

jumps

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

#define sz 200005
int n;
vector<int> v;
int dp[sz];

int tree[sz*3];

void Init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node] = v[b];
        return ;
    }
    int lft = node*2;
    int rgt = node*2+1;
    int mid = (b+e)/2;

    Init(lft,b,mid);
    Init(rgt,mid+1,e);

    tree[node] = max(tree[lft] ,tree[rgt]);
}

int Query(int node,int b,int e,int i,int j)
{
    if(i>e || j<b)
        return 0;
    if(b>=i && e<=j)
        return tree[node];

    int mid = (b+e)/2;
    int sum1 = Query(node*2,b,mid,i,j);
    int sum2 = Query(node*2+1,mid+1,e,i,j);

    return max(sum1,sum2);
}


void init(int N, std::vector<int> H) {

    int i;
    n = N;
    v.push_back(0);
    for(i=0;i<N;i++){
        v.push_back(H[i]);
    }
    Init(1,1,n);
}

int FuN(int last,int C,int D)
{
    if(last>=C && last<=D){
        return 0;
    }
    if(dp[last]!=-1)
        return dp[last];
    int ret = 1e9;

    int lo=last+1,hi=n,mid,res=-1;
    while(lo<=hi)
    {
        mid = (lo+hi)/2;
        if(Query(1,1,n,last+1,mid)>v[last])
        {
            res = mid;
            hi = mid-1;
        }
        else
            lo = mid+1;
    }
    if(res!=-1)
        ret = min(ret,1+FuN(res,C,D));

    lo=1,hi=last-1,mid,res=-1;
    while(lo<=hi)
    {
        mid = (lo+hi)/2;
        if(Query(1,1,n,mid,last-1)>v[last])
        {
            res = mid;
            lo = mid+1;
        }
        else
            hi = mid-1;
    }
    if(res!=-1)
        ret = min(ret,1+FuN(res,C,D));
    return dp[last] = ret;
}

int minimum_jumps(int A, int B, int C, int D) {

  memset(dp,-1,sizeof(dp));
  int ans=1e9;
  A++;
  B++;
  C++;
  D++;
  for(int i=A;i<=B;i++){
    ans = min(ans,FuN(i,C,D));
  }
  if(ans==1e9)
    ans = -1;
  return ans;
}

Compilation message (stderr)

jumps.cpp: In function 'int FuN(int, int, int)':
jumps.cpp:80:29: warning: right operand of comma operator has no effect [-Wunused-value]
   80 |     lo=1,hi=last-1,mid,res=-1;
      |                             ^

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19