Submission #1175314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175314		mactoddlover	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	595 ms	59952 KiB

jumps

#include<bits/stdc++.h>

#define fi first
#define se second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)(v).size()

#define endl "\n"
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;

const int MAX = 2e5 + 5;
const int lg = 17;

int N, Q, H[MAX];
int l[MAX][lg+1], r[MAX][lg+1], nxt[MAX][lg+1], spt[MAX][lg+1];

int combine(int i, int j){
    return H[i] < H[j] ? j : i;
}

void init(int _N, vector<int> _H){
    N = _N;
    for(int i = 0; i < N; i++) H[i+1] = _H[i];

    stack<int> st;

    for(int i = 1; i <= N; i++){
        while(!st.empty() && H[i] > H[st.top()]) st.pop();
        l[i][0] = st.empty() ? -1 : st.top();
        st.push(i);
    }

    while(!st.empty()) st.pop();

    for(int i = N; i >= 1; i--){
        while(!st.empty() && H[i] > H[st.top()]) st.pop();
        r[i][0] = st.empty() ? -1 : st.top();
        st.push(i);
    }

    for(int i = 1; i <= N; i++){
        spt[i][0] = i;
        nxt[i][0] = -1;
        if(l[i][0] != -1 && r[i][0] != -1) nxt[i][0] = combine(l[i][0], r[i][0]);
        else if(l[i][0] != -1) nxt[i][0] = l[i][0];
        else if(r[i][0] != -1) nxt[i][0] = r[i][0];
    }

    for(int j = 1; j <= lg; j++){
        for(int i = 1; i <= N; i++){
            l[i][j] = (l[i][j-1] == -1 ? -1 : l[l[i][j-1]][j-1]);
            r[i][j] = (r[i][j-1] == -1 ? -1 : r[r[i][j-1]][j-1]);
            nxt[i][j] = (nxt[i][j-1] == -1 ? -1 : nxt[nxt[i][j-1]][j-1]);
            if(i + (1 << j) - 1 <= N){//sparse table max
                spt[i][j] = combine(spt[i][j-1], spt[i + (1 << (j-1))][j-1]);
            }
        }
    }
}

int get(int l, int r){
    if(l > r) return -1;
    int k = __lg(r - l + 1);
    return combine(spt[l][k], spt[r - (1 << k) + 1][k]);
}

int minimum_jumps(int a, int b, int c, int d){
    a++, b++, c++, d++;

    int answer = 0;

    int idx_max_cd = get(c, d);
    int idx_max_bc = get(b + 1, c - 1);

    int limit_end = H[idx_max_cd];
    int limit_middle = (idx_max_bc == -1 ? -1 : H[idx_max_bc]);

    int st = b;

    for(int j = lg; j >= 0; j--){
        if(l[st][j] != -1 && l[st][j] >= a && H[l[st][j]] < limit_end){
            st = l[st][j];
        }
    }

    for(int j = lg; j >= 0; j--){
        if(nxt[st][j] != -1 && H[nxt[st][j]] < limit_middle){
            answer += (1 << j);
            st = nxt[st][j];
        }
    }

    auto inside = [&](int l, int r, int x) -> bool{
        return l <= x && x <= r;
    };

    // H[st] > H[middle] -> try to jump in 1
    if(r[st][0] != -1 && inside(c, d, r[st][0])) return answer + 1;
    // H[st] < H[middle] -> try to step back one and then go for the clutch
    // more than 1 step back are useless since the more we go left, the value will increase -> out of bound [c, d]
    if(l[st][0] != -1 && inside(c, d, r[l[st][0]][0])) return answer + 2;

    //st --> middle --> r[middle][0]
    for(int j = lg; j >= 0; j--){
        if(r[st][j] != -1 && H[r[st][j]] <= limit_middle){
            answer += (1 << j);
            st = r[st][j];
        }
    }

    return inside(c, d, r[st][0]) ? answer + 1 : -1;
}

#ifdef LOCAL
void fastIO(){
    ios_base::sync_with_stdio(NULL); cin.tie(0);
    freopen("task.INP", "r", stdin);
    freopen("task.OUT", "w", stdout);
}

signed main(){
    fastIO();

    init(7, {3, 2, 1, 6, 4, 5, 7});

    cout << minimum_jumps(0, 1, 2, 2);
}
#endif

• 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