Submission #478306

#	Time	Username	Problem	Language	Result	Execution time	Memory
478306		couplefire	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1541 ms	52900 KiB

jumps

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

const int N = 200005;

int n, h[N], r_nxt[N], l_nxt[N], nxt[N], r_up[N][20], l_up[N][20], up[N][20];

void init(int N, vector<int> H){
    n = N;
    for(int i = 1; i<=n; ++i)
        h[i] = H[i-1];
    h[0] = h[n+1] = n+1;
    stack<int> st; st.push(0);
    for(int i = 1; i<=n; ++i){
        while(h[st.top()]<h[i]) st.pop();
        l_nxt[i] = st.top(); st.push(i);
    } l_nxt[0] = 0;
    while(st.size()) st.pop();
    st.push(n+1);
    for(int i = n; i>=1; --i){
        while(h[st.top()]<h[i]) st.pop();
        r_nxt[i] = st.top(); st.push(i);
    } r_nxt[n+1] = n+1;
    for(int i = 1; i<=n+1; ++i)
        if(!l_nxt[i]) nxt[i] = r_nxt[i];
        else if(r_nxt[i]==n+1) nxt[i] = l_nxt[i];
        else if(h[r_nxt[i]]>h[l_nxt[i]]) nxt[i] = r_nxt[i];
        else nxt[i] = l_nxt[i];
    for(int i = 0; i<=n; ++i){
        l_up[i][0] = l_nxt[i];
        for(int j = 1; j<20; ++j)
            l_up[i][j] = l_up[l_up[i][j-1]][j-1];
    }
    for(int i = n+1; i>=1; --i){
        r_up[i][0] = r_nxt[i];
        for(int j = 1; j<20; ++j)
            r_up[i][j] = r_up[r_up[i][j-1]][j-1];
    }
    for(int i = 1; i<=n+1; ++i)
        up[i][0] = nxt[i];
    for(int j = 1; j<20; ++j)
        for(int i = 1; i<=n+1; ++i)
            up[i][j] = up[up[i][j-1]][j-1];
}

int minimum_jumps(int a, int b, int c, int d){
    ++a; ++b; ++c; ++d;
    int big;
    {
        int v = b;
        for(int i = 19; i>=0; --i)
            if(r_up[v][i]<=d) v = r_up[v][i];
        if(v<c) return -1;
        big = v;
    }
    int start;
    {
        int v = b;
        for(int i = 19; i>=0; --i)
            if(l_up[v][i]>=a && h[l_up[v][i]]<=h[big]) v = l_up[v][i];
        start = v;
    }
    int smol;
    {
        int v = start;
        for(int i = 19; i>=0; --i)
            if(r_up[v][i]<c) v = r_up[v][i];
        smol = r_nxt[v];
    }
    int bruh, step = 0;
    {
        int v = start;
        for(int i = 19; i>=0; --i)
            if(h[up[v][i]]<h[smol]) v = up[v][i], step += (1<<i);
        bruh = v;
    }
    int ans = 1e9;
    {
        int tmp = step;
        int v = bruh;
        for(int i = 19; i>=0; --i)
            if(r_up[v][i]<c) v = r_up[v][i], tmp += (1<<i);
        ++tmp; ans = min(ans, tmp);
    }
    if(l_nxt[bruh] && h[l_nxt[bruh]]<h[big] && h[l_nxt[bruh]]>h[smol]) ans = min(ans, step+2);
    return ans;
}

• 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