Submission #738743

#	Time	Username	Problem	Language	Result	Execution time	Memory
738743		Kenjikrab	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1454 ms	45848 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
int const n_max=2e5+10;
int const h_max=18;
int rit[n_max][h_max],lef[n_max][h_max],hi[n_max][h_max];
int n;
vector<int> a;

void init(int N, vector<int> H) {
    a=H;
    stack<int>st;
    for(int i=0; i<N; ++i) {
        lef[i][0] = rit[i][0] = hi[i][0] = i;
    }
    for(int i=0; i<N; ++i) {
        while(!st.empty() && H[st.top()]<a[i]) {
            rit[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }

    while(!st.empty()) st.pop();
    for(int i=N-1; i>=0; --i) {
        while(!st.empty() && H[st.top()]<a[i]) {
            lef[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }

    for(int i=0; i<N; ++i) {
        hi[i][0] = (H[lef[i][0]]>H[rit[i][0]]) ? lef[i][0] : rit[i][0];
    }

    for(int j=1; j<h_max; ++j) {
        for(int i=0; i<N; ++i) {
            lef[i][j] = lef[lef[i][j-1]][j-1];
            rit[i][j] = rit[rit[i][j-1]][j-1];
            hi[i][j] = hi[hi[i][j-1]][j-1];
        }
    }
}
/*
void init(int N, vector<int> H)
{
    n=N;
    a=H;
    stack<int> stk;
    for(int i=0;i<n;i++)lef[i][0]=rit[i][0]=i;
    for(int i=0;i<n;i++)
    {
        while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
        if(stk.empty()) lef[i][0]=i;
        else lef[i][0]=stk.top();
        stk.push(i);
    }
    while(!stk.empty())stk.pop();
    for(int i=n-1;i>=0;i--)
    {
        while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
        if(stk.empty()) rit[i][0]=i;
        else rit[i][0]=stk.top();
        stk.push(i);
    }
    for(int i=0;i<n;i++)
    {
        hi[i][0]=(a[lef[i][0]]>a[rit[i][0]])? lef[i][0]:rit[i][0];
    }
    for(int i=1;i<h_max;i++)
    {
        for(int j=0;j<n;j++)
        {
            lef[j][i]=lef[rit[j][i-1]][i-1];
            rit[j][i]=rit[rit[j][i-1]][i-1];
            hi[j][i]=hi[hi[j][i-1]][i-1];
        }
    }
}

int find_mx(int C,int D)
{
    int cur=C;
    for(int i=h_max-1;i>=0;i--)
    {
        if(rit[cur][i]<=D) cur=rit[cur][i];
    }
    return a[cur];
}
int find_st(int A,int B,int mx)
{
    int cur=A;
    for(int i=h_max-1;i>=0;i--)
    {
        if(rit[cur][i]<=B&&a[rit[cur][i]]<mx) cur=rit[cur][i];
    }
    return a[cur];
}
int find_dis(int cur,int C,int D)
{
    int ret=0;
    for(int i=h_max-1;i>=0;i--)
    {
        if(rit[cur][i]>=C)continue;
        cur=rit[cur][i];
        ret+=1<<i;
    }
    ret++;
    cur=rit[cur][0];
    if(C<=cur&&cur<=D)return ret;
    return -1;
}
*/
int find_mx(int C, int D) {
    int cur = C;
    for(int j=h_max-1; j>=0; --j) {
        if(rit[cur][j]<=D) {
            cur = rit[cur][j];
        }
    }
    return a[cur];
}
int find_st(int A, int B, int mx) {
    int cur = B;
    for(int j=h_max-1; j>=0; --j) {
        if(lef[cur][j]>=A && a[lef[cur][j]]<mx) {
            cur = lef[cur][j];
        }
    }
    return cur;
}
int find_dis(int cur, int C, int D) {
    int ret = 0;
    for(int j=h_max-1; j>=0; --j) {
        if(rit[cur][j]<C) {
            ret |= 1<<j;
            cur = rit[cur][j];
        }
    }
    ++ret;
    cur = rit[cur][0];
    if(cur>=C && cur<=D) return ret;
    return -1;
}
int minimum_jumps(int A, int B, int C, int D)
{
    int mx=find_mx(C,D);
    int st=find_st(A,B,mx);
    if(a[st]>mx)return -1;
    int ans=0;
    int cur=st;
    for(int i=h_max-1;i>=0;i--)
    {
        if(a[hi[cur][i]]>=mx)continue;
        if(rit[hi[cur][i]][0]>=C)continue;
        cur=hi[cur][i];
        ans+=1<<i;
    }
    int add=find_dis(cur,C,D);
    if(a[hi[cur][0]]<=mx)
    {
        int nadd=find_dis(hi[cur][0],C,D);
        if(nadd!=-1)add=min(add,nadd+1);
    }
    if(add==-1)return -1;
    return ans+add;
}

• 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