Submission #1282055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282055		duckindog	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	411 ms	33324 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200'000 + 10,
            MAX = 1'000'000,
            LG = 17;

int n;
int h[MAXN];

int goL[MAXN], goR[MAXN];
int up[MAXN][LG + 1], upR[MAXN][LG + 1];
void init(int N, std::vector<int> H) {
    n = N;
    for (int i = 0; i < n; ++i) h[i] = H[i];
    { // go left
        stack<int> st;
        for (int i = 0; i < n; ++i) { 
            while (st.size() && h[st.top()] < h[i]) st.pop();
            goL[i] = (st.size() ? st.top() : n);
            st.push(i);
        }
    }
    { // go right
        stack<int> st;
        for (int i = n - 1; i >= 0; --i) { 
            while (st.size() && h[st.top()] < h[i]) st.pop();
            goR[i] = (st.size() ? st.top() : n);
            st.push(i);
        }
    }
    
    h[n] = -1;
    fill(up[n], up[n] + LG + 1, n);
    for (int i = 0; i < n; ++i) { 
        up[i][0] = (h[goR[i]] > h[goL[i]] ? goR[i] : goL[i]);
    }
    
    h[n] = MAX;
    fill(upR[n], upR[n] + LG + 1, n);
    for (int i = 0; i < n; ++i) { 
        upR[i][0] = (h[goR[i]] < h[goL[i]] ? goR[i] : goL[i]);
    }

    for (int j = 1; j <= LG; ++j) { 
        for (int i = 0; i < n; ++i) { 
            up[i][j] = up[up[i][j - 1]][j - 1];
            upR[i][j] = upR[upR[i][j - 1]][j - 1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int ret = 0;
    for (int j = LG; j >= 0; --j) { 
        if (h[up[A][j]] <= h[C]) { 
            ret += (1 << j);
            A = up[A][j];
        }
    }
    for (int j = LG; j >= 0; --j) { 
        if (h[upR[A][j]] <= h[C]) { 
            ret += (1 << j);
            A = upR[A][j];
        }
    }
    
    return A == C ? ret : -1;
}

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