Submission #1282162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282162		Art	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	506 ms	49760 KiB

jumps

//      - Art -
#include "jumps.h"
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)

const int N = 2e5 + 7;

using namespace std;

int n, L[N][20], R[N][20];
int nxt[N][20];

void init(int _n, vector<int> h) {
    n = _n;
    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.emplace(i);
    }
    while (!st.empty()) {
        st.pop();
    }
    REV (i, n - 1, 0) {
        while (!st.empty() && h[st.top()] <= h[i]) {
            st.pop();
        }
        R[i][0] = st.empty() ? n : st.top();
        st.emplace(i);
    }
    h.emplace_back(0);
    REP (i, n) {
        nxt[i][0] = (h[L[i][0]] > h[R[i][0]] ? L[i][0] : R[i][0]);
    }
    REP (i, 20) {
        L[n][i] = R[n][i] = nxt[n][i] = n;
    }
    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];
        nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
//        cout << L[i][j] << ' ' << L[i][j - 1], el;
    }
}

int dist[N];

int minimum_jumps(int a, int b, int c, int d) {
    REV (i, 19, 0) {
        if (L[b][i] >= a && R[L[b][i]][0] <= d) {
            b = L[b][i];
        }
    }
    if (R[b][0] >= c && R[b][0] <= d) {
        return 1;
    }
    int res = 0;
    REV (i, 19, 0) if (R[nxt[b][i]][0] < c) {
        b = nxt[b][i];
        res += 1 << i;
    }
    if (R[nxt[b][0]][0] <= d) {
        return res + 2;
    }
    REV (i, 19, 0) if (R[b][i] < c) {
        b = R[b][i];
        res += 1 << i;
    }
    return (c <= R[b][0] && R[b][0] <= d ? res + 1 : -1);
}

#ifdef ONLINE_JUDGE
int main() {

    #define name "art"
    if (fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> h(n);
    REP (i, n) {
        cin >> h[i];
    }
    init(n, h);
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d), el;
    }

    return 0;
}
#endif // ONLINE_JUDGE

• 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