Submission #740830

#	Time	Username	Problem	Language	Result	Execution time	Memory
740830		nguyentunglam	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1376 ms	47896 KiB

jumps

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 2e5 + 10;
int l[N], r[N], h[N], sp[20][N], lg[N], pos[N], f[20][N], g[20][N];
int n ;

int getmax(int l, int r) {
    int k = lg[r - l + 1];
    int x = sp[k][l], y = sp[k][r - (1 << k) + 1];
    return h[x] > h[y] ? x : y;
}

void init(int _n, vector<int> H) {
    stack<int> st;
    n = _n;
    h[n] = 1e9;
    for(int i = 0; i < n; i++) h[i] = H[i], pos[h[i]] = i, sp[0][i] = i;
    for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for(int j = 1; j <= lg[n]; j++) for(int i = 0; i + (1 << j) - 1 < n; i++) {
        int x = sp[j - 1][i], y = sp[j - 1][i + (1 << j >> 1)];
        sp[j][i] = h[x] > h[y] ? x : y;
    }

    for(int i = 0; i < n; i++) {
        while (!st.empty() && h[st.top()] < h[i]) st.pop();
        l[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--) {
        while (!st.empty() && h[st.top()] < h[i]) st.pop();
        r[i] = st.empty() ? n : st.top();
        st.push(i);
        if (h[l[i]] > h[r[i]]) swap(l[i], r[i]);
    }
    for(int j = 0; j <= lg[n]; j++) f[j][n] = g[j][n] = n;
    for(int val = n; val >= 1; val--) {
        int i = pos[val];
        f[0][i] = r[i]; g[0][i] = l[i];
        for(int j = 1; j <= lg[n]; j++) {
            f[j][i] = f[j - 1][f[j - 1][i]];
            g[j][i] = g[j - 1][g[j - 1][i]];
        }

    }
    h[n + 1] = 0;
}


int minimum_jumps(int a, int b, int c, int d) {
    if (max(a, c) <= min(b, d)) return 0;
    int ret = 0;
    int ed = getmax(c, d);
    int L = a, R = b, last = n + 1;
    while (L <= R) {
        int mid = L + R >> 1;
        if (h[getmax(mid, b)] < h[ed]) {
            R = mid - 1;
            last = mid;
        }
        else L = mid + 1;
    }
    if (last == n + 1) return - 1;

    int st = getmax(last, b);

    if (b + 1 == c) return 1;
    int block = getmax(b + 1, c - 1);
    if (h[block] > h[ed]) return -1;
    if (h[st] > h[block]) return 1;

    for(int j = lg[n]; j >= 0; j--) if (h[f[j][st]] < h[block]) {
        st = f[j][st];
        ret += (1 << j);
    }

    if (h[r[st]] < h[ed]) return ret + 2;

    for(int j = lg[n]; j >= 0; j--) if (h[g[j][st]] <= h[block]) {
        st = g[j][st];
        ret += (1 << j);
    }
    return ret + 1;
}

#ifdef ngu
int main() {
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    int n; cin >> n;
    vector<int> h;
    h.resize(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) << endl;
    }
}
#endif // ngu

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         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