Submission #952707

#	Time	Username	Problem	Language	Result	Execution time	Memory
952707		onepunchac168	Rainforest Jumps (APIO21_jumps)	C++14	4 / 100	763 ms	22992 KiB

jumps

#include "jumps.h"

#include <vector>

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

#define pb push_back
#define fi first
#define se second
#define mask(x) (1<<x)
typedef int ll;
typedef pair <ll,ll> ii;
const int N=2e5+5;
ll nxtb[N];
ll nxta[N];
int n;
ll a[N];
ll mx[20][N];
ll pos[N];
ll sa[N],sb[N];
ll get(int u,int v)
{
    ll kc=log2(v-u+1);
    //cout<<u<<" "<<v<<" "<<kc<<" "<<mx[kc][u]<<" "<<mx[kc][v-mask(kc)+1]<<" "<<v<<" "<<mask(kc)<<'\n';
    return max(mx[kc][u],mx[kc][v-mask(kc)+1]);
}
void init(int N, std::vector<int> H)
{
    stack <ll> st;
    n=N;
    for (int i=1;i<=n;i++)
    {
        a[i]=H[i-1];
        pos[a[i]]=i;
    }
    for (int i=1;i<=n;i++)
    {
        while (!st.empty()&&a[st.top()]<=a[i])
        {
            st.pop();
        }
        if (!st.empty())
        {
            nxta[i]=st.top();
        }
        else nxta[i]=0;
        sa[i]=sa[nxta[i]]+1;
        st.push(i);
    }
    while (!st.empty())
    {
        st.pop();
    }
    for (int i=n;i>=1;i--)
    {
        while (!st.empty()&&a[st.top()]<=a[i])
        {
            st.pop();
        }
        if (!st.empty())
        {
            nxtb[i]=st.top();
        }
        else nxtb[i]=n+1;
        sb[i]=sb[nxtb[i]]+1;
        st.push(i);
        mx[0][i]=a[i];
    }
    for (int i=1;i<=18;i++)
    {
        for (int j=1;j<=n;j++)
        {
            mx[i][j]=max(mx[i-1][j],mx[i-1][j+mask(i-1)]);
        }
    }
}
const char nl='\n';
int minimum_jumps(int A, int B, int C, int D)
{
    A++;
    B++;
    C++;
    D++;
    ll aa=get(C,D);
    int left=A;
    int right=B;
    int ans=-1;
    int gmax=1e9+5;
    while (left<=right)
    {
        int mid=(left+right)/2;
        if (get(mid,C-1)<aa)
        {
            ans=mid;
            right=mid-1;
        }
        else left=mid+1;
    }
    //cout<<nl;
    if (ans!=-1)
    {
        ll bb=pos[get(ans,B)];
        ll cc=get(bb,C-1);
        int left=C;
        int res;
        int right=D;
        while (left<=right)
        {
            int mid=(left+right)/2;
            if (get(C,mid)>cc)
            {
                res=mid;
                right=mid-1;
            }
            else left=mid+1;
        }
        gmax=min(gmax,sb[bb]-sb[res]);
    }
    left=1;
    right=A-1;
    int a1=get(A,C-1);
    ans=-1;
    while (left<=right)
    {
        int mid=(left+right)/2;
        if (get(mid,C-1)>a1)
        {
            ans=mid;
            left=mid+1;
        }
        else right=mid-1;
    }
    if (ans!=-1)
    {
        ll bb=pos[get(A,B)];
        if (a[ans]<aa)
        {
            gmax=min(gmax,sa[bb]-sa[ans]+1);
        }
    }
    if (gmax==1e9+5)
    {
        return -1;
    }
    return gmax;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:74:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   74 |             mx[i][j]=max(mx[i-1][j],mx[i-1][j+mask(i-1)]);
      |                                                    ~^~
jumps.cpp:11:21: note: in definition of macro 'mask'
   11 | #define mask(x) (1<<x)
      |                     ^
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:118:36: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |         gmax=min(gmax,sb[bb]-sb[res]);
      |                              ~~~~~~^

• 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