Submission #952834

#	Time	Username	Problem	Language	Result	Execution time	Memory
952834		onepunchac168	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1022 ms	77940 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 nxt[N][20];
vector <ll> adj[N];
ll cha[N][20];

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 dfs(int u)
{
    for (auto v:adj[u])
    {
        cha[v][0]=u;
        for (int i=1;i<=18;i++)
        {
            cha[v][i]=cha[cha[v][i-1]][i-1];
        }
        sa[v]=sa[u]+1;
        dfs(v);
    }
}
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];
        if (nxtb[i]!=n+1)
        {
            ll rr=nxta[i];
            if (a[nxta[i]]<a[nxtb[i]])
            {
                rr=nxtb[i];
            }
            nxta[i]=rr;
        }
        ll rr=nxta[i];
        if (rr!=0&&rr!=n+1)
        {
            adj[rr].pb(i);
        }
        nxt[i][0]=nxtb[i];
        for (int j=1;j<=18;j++)
        {
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
        }
    }
    dfs(pos[n]);
    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]);
    }
    ll bb=pos[get(A,B)];
    ll dd=0;
    ll hh=0;
    if (B+1<=C-1){hh=get(B+1,C-1);}
    for (int i=18;i>=0;i--)
    {
        if (cha[bb][i]==0)
        {
            continue;
        }
        if (cha[bb][i]<C&&a[cha[bb][i]]<hh)
        {
            dd+=mask(i);
            bb=cha[bb][i];
        }
    }
    if (a[bb]<hh&&a[cha[bb][0]]<aa)
    {
        bb=cha[bb][0];
        dd++;
    }
    if (bb!=0&&bb<C&&a[bb]<aa)
    {
        for (int i=18;i>=0;i--)
        {
            if (nxt[bb][i]>=1&&nxt[bb][i]<=n)
            {
                if (nxt[bb][i]<C)
                {
                    bb=nxt[bb][i];
                    dd+=mask(i);
                }
            }
        }
        //cout<<A<<" "<<C<<" "<<bb<<" "<<dd<<" "<<"ok"<<nl;
        bb=nxt[bb][0];
        if (bb>=C&&bb<=D){
            gmax=min(gmax,dd+1);
        }
    }
    if (gmax==1e9+5)
    {
        return -1;
    }
    return gmax;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:111:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  111 |             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:155:36: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  155 |         gmax=min(gmax,sb[bb]-sb[res]);
      |                              ~~~~~~^

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