Submission #1302798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302798		icebear	Rainforest Jumps (APIO21_jumps)	C++20	48 / 100	491 ms	66200 KiB

jumps

/* AUTHOR: TUAN ANH - BUI */
// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) return x = y, true;
        return false;
    }

template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) return x = y, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
/*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */

const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 27092008;
const ll INF  = (ll)1e18 + 27092008;
const int N = 2e5 + 5;
int h[N], L[N][20], R[N][20], high[N][20], low[N][20];

void init(int N, vector<int> H) {
    REP(i, N) h[i] = H[i];

    stack<int> st;
    REP(i, N) {
        while(!st.empty() && H[st.top()] < H[i]) st.pop();
        L[i][0] = (st.empty() ? N : st.top());
        st.push(i);
    }

    st = stack<int>();
    RED(i, N) {
        while(!st.empty() && H[st.top()] < H[i]) st.pop();
        R[i][0] = (st.empty() ? N : st.top());
        st.push(i);
    }

    REP(i, N) {
        if (H[L[i][0]] > H[R[i][0]]) {
            high[i][0] = L[i][0];
            low[i][0] = R[i][0];
        } else {
            high[i][0] = R[i][0];
            low[i][0] = L[i][0];
        }
    }

    REP(j, 20) L[N][j] = R[N][j] = high[N][j] = low[N][j] = N;
    h[N] = inf;
    FOR(j, 1, 19) REP(i, N) {
        L[i][j] = L[L[i][j - 1]][j - 1];
        R[i][j] = R[R[i][j - 1]][j - 1];
        low[i][j] = low[low[i][j - 1]][j - 1];
        high[i][j] = high[high[i][j - 1]][j - 1];
    }
}

int get_max(int left, int right, int limit) {
    RED(j, 20) if (L[right][j] >= left && h[L[right][j]] < limit)
        right = L[right][j];
    return right;
}

int minimum_jumps(int A, int B, int C, int D) {
    int ans = 0, max_right = get_max(C, D, inf), max_left = get_max(A, B, h[max_right]);

    RED(j, 20) if (h[high[max_left][j]] < h[max_right] && high[max_left][j] < C) {
        ans += MASK(j);
        max_left = high[max_left][j];
    }

    if (C <= high[max_left][0] && high[max_left][0] <= D) return ans + 1;

    RED(j, 20) if (h[R[max_left][j]] < h[max_right] && R[max_left][j] < C) {
        ans += MASK(j);
        max_left = R[max_left][j];
    }

    return (C <= R[max_left][0] && R[max_left][0] <= D ? ans + 1 : -1);
}

// int main() {
//     init(7, {3, 2, 1, 6, 4, 5, 7});
//     cout << minimum_jumps(4, 4, 6, 6) << '\n' << minimum_jumps(1, 3, 5, 6) << '\n' << minimum_jumps(0, 1, 2, 2);
//     return 0;
// }

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