Submission #960846

#	Time	Username	Problem	Language	Result	Execution time	Memory
960846		peterandvoi	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	891 ms	47712 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mxN = (int) 2e5 + 5;
const int LOG = 18;

int N;
int H[mxN], lg[mxN], pos[mxN];
int R[LOG][mxN], B[LOG][mxN], spt[LOG][mxN];

int cmb(int i, int j) {
    return H[i] > H[j] ? i : j;
}

void init(int n, std::vector<int> h) {
    N = n;
    for (int i = 0; i < N; ++i) {
        H[i + 1] = h[i];
        pos[h[i]] = i + 1;
    }
    H[0] = H[n + 1] = n + 1;
    vector<int> st;
    st.emplace_back(n + 1);
    for (int i = n; i >= 1; --i) {
        while (st.size() && H[i] >= H[st.back()]) {
            st.pop_back();
        }
        R[0][i] = st.back();
        st.emplace_back(i);
    }
    while (st.size()) {
        st.pop_back();
    }
    st.emplace_back(0);
    for (int i = 1; i <= n; ++i) {
        while (st.size() && H[i] >= H[st.back()]) {
            st.pop_back();
        }
        if (i > 1) {
            lg[i] = lg[i / 2] + 1;
        }
        spt[0][i] = H[i];
        B[0][i] = cmb(R[0][i], st.back());
        st.emplace_back(i);
    }
    for (int i = 1; i <= lg[n]; ++i) {
        for (int j = 1; j <= n; ++j) {
            B[i][j] = B[i - 1][B[i - 1][j]];
            R[i][j] = R[i - 1][R[i - 1][j]];
            if (j + (1 << i) - 1 <= n) {
                spt[i][j] = max(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
}

int get(int l, int r) {
    int k = lg[r - l + 1];
    return max(spt[k][l], spt[k][r - (1 << k) + 1]);
}

int minimum_jumps(int a, int b, int c, int d) {
    a++, b++, c++, d++;
    int l = a, r = b, s = -1;
    int Hr = get(c, d);
    while (l <= r) {
        int mid = l + r >> 1;
        int Hl = get(mid, b);
        if (Hl < Hr) {
            s = pos[Hl];
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    if (s == -1) {
        return -1;
    }
    if (b + 1 == c) {
        return 1;
    }
    int Hmid = get(b + 1, c - 1);
    if (H[s] > Hmid) {
        return 1;
    }
    if (Hmid > Hr) {
        return -1;
    }
    int res = 0;
    for (int i = lg[N]; i >= 0; --i) {
        if (H[B[i][s]] < Hmid) {
            s = B[i][s];
            res += 1 << i;
        }
    }
    if (H[B[0][s]] < Hr) {
        return res + 2;
    }
    for (int i = lg[N]; i >= 0; --i) {
        if (H[R[i][s]] < Hmid) {
            s = R[i][s];
            res += 1 << i;
        }
    }
    return res + 2;
}

#ifdef ngu
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    init(n, h);
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d) << "\n";
    }
}
#endif

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = l + r >> 1;
      |                   ~~^~~

• 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