Submission #551952

#	Time	Username	Problem	Language	Result	Execution time	Memory
551952		marsxiang5902	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1263 ms	54240 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

const int MN = 2e5+5, ML = 18;

int N, sptb[ML][MN], *ar = sptb[0], ainv[MN], nxL[MN], bl[ML][MN], blR[ML][MN], *nxR = blR[0];

int queMx(int l, int r){
    assert(l <= r);
    int d = __lg(r-l+1);
    return max(sptb[d][l], sptb[d][r-(1<<d)+1]);
}

void init(int _N, vector<int> _ar){
    N = _N; memcpy(ar+1, &_ar[0], N * sizeof ar[0]);
    set<int> st = {0, N+1};
    ar[0] = N+1; ar[N+1] = N+2;
    for(int i = 0; i <= N+1; i++)
        ainv[--ar[i]] = i;
    for(int val = N+1; val--; ){
        int pos = ainv[val];
        auto it = st.insert(pos).first;
        int l = *prev(it), r = *next(it);
        nxL[pos] = l;
        nxR[pos] = r;
        bl[0][pos] = ainv[max(ar[l], ar[r])];
    }
    nxL[0] = 0; nxR[0] = nxL[N+1] = nxR[N+1] = bl[0][0] = bl[0][N+1] = N+1;
    for(int l = 1; l < ML; l++)
        for(int i = 0; i <= N+1; i++){
            bl[l][i] = bl[l-1][bl[l-1][i]],
            blR[l][i] = blR[l-1][blR[l-1][i]];
        }
    for(int l = 1; l < ML; l++)
        for(int i = 0; i+(1<<l)-1 <= N+1; i++)
            sptb[l][i] = max(sptb[l-1][i], sptb[l-1][i+(1<<l-1)]);
}

int minimum_jumps(int a, int b, int c, int d){
    ++a; ++b; ++c; ++d;
    int idxR = ainv[queMx(c, d)], midMx = b+1 <= c-1 ? queMx(b+1, c-1) : -1;
    a = max(a, nxL[idxR] + 1);
    if(b < a || midMx > ar[idxR]) return -1;
    int idxL = ainv[queMx(a, b)], ans = 0;
    assert(ar[idxL] < ar[idxR]);
    for(int l = ML; l--; )
        if(ar[bl[l][idxL]] <= midMx){
            idxL = bl[l][idxL];
            ans += 1<<l;
        }
    assert(ar[idxL] < ar[idxR]);
    if(nxR[idxL] < c && ar[nxL[idxL]] > ar[nxR[idxL]] && ar[nxL[idxL]] < ar[idxR]){
        idxL = nxL[idxL];
        ++ans;
    }
    assert(ar[idxL] < ar[idxR]);
    for(int l = ML; l--; )
        if(ar[blR[l][idxL]] <= midMx){
            idxL = blR[l][idxL];
            ans += 1<<l;
        }
    assert(c <= nxR[idxL] && nxR[idxL] <= d);
    return ans + 1;
}

#ifdef LOCAL_PROJECT
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N, Q; cin >> N >> Q;
    vector<int> ar(N);
    for(int &x: ar)
        cin >> x;
    init(N, ar);
    for(int i = 0, a, b, c, d; i < Q; i++){
        cin >> a >> b >> c >> d;
        printf("%d\n", minimum_jumps(a, b, c, d));
    }

    return 0;
}
#endif

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:36:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |             sptb[l][i] = max(sptb[l-1][i], sptb[l-1][i+(1<<l-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