Submission #1274769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274769		nguyenkhangninh99	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	524 ms	90128 KiB

jumps

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

const int LG = 19, maxn = 2e5 + 5;
pair<int, int> maxjump[LG][maxn], minjump[LG][maxn], spmax[LG][maxn];
pair<int, int> get(int l, int r){
    int k = __lg(r - l + 1);
    return max(spmax[k][l], spmax[k][r - (1 << k) + 1]);
}

int n, q;
vector<int> h, l, r;
void init(int N, vector<int> H){
    n = N;
    h.assign(n + 1, 0);
    l.assign(n + 1, -1);
    r.assign(n + 1, -1);
    for(int i = 1; i <= n; i++) h[i] = H[i - 1];

    {
        vector<int> st;
        for(int i = 1; i <= n; i++){
            while(st.size() && h[st.back()] <= h[i]) st.pop_back();
            if(st.size()) l[i] = st.back();
            st.push_back(i);
        }
    }
    {
        vector<int> st;
        for(int i = n; i >= 1; i--){
            while(!st.empty() && h[st.back()] <= h[i]) st.pop_back();
            if(!st.empty()) r[i] = st.back();
            st.push_back(i);
        }
    }

    for(int i = 1; i <= n; i++){
        priority_queue<pair<int, int>> pq;
        if(l[i] != -1) pq.push({h[l[i]], l[i]});
        if(r[i] != -1) pq.push({h[r[i]], r[i]});
        if(pq.size()){
            maxjump[0][i] = pq.top();
            pq.pop();
        }if(pq.size()){
            minjump[0][i] = pq.top();
            pq.pop();
        } 
        spmax[0][i] = {h[i], i};
    }

    for(int j = 1; j < LG; j++){
        for(int i = 1; i <= n; i++){
            maxjump[j][i] = maxjump[j - 1][ maxjump[j - 1][i].second ];
            minjump[j][i] = minjump[j - 1][ minjump[j - 1][i].second ];
        }
        for(int i = 1; i + (1 << j) - 1 <= n; i++) spmax[j][i] = max(spmax[j - 1][i], spmax[j - 1][i + (1 << (j - 1))]);
    }
}

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

    if(c == b + 1){
        if(h[b] < get(c, d).first) return 1;
        else return -1;
    }

    int r = b, peak = get(c, d).second, block = get(b + 1, c - 1).second, rpos = l[block];
    if(h[block] >= h[peak]) return -1;
    
    for(int i = LG - 1; i >= 0; i--){
        if(r - (1 << i) >= a && get(r - (1 << i), b).first < h[block]) r -= (1 << i);
    }
    int cur = get(r, b).second, res = 0;
    for(int i = LG - 1; i >= 0; i--){
        if(maxjump[i][cur].second && maxjump[i][cur].first <= h[block]){
            cur = maxjump[i][cur].second;
            res += (1 << i);
        }
    }
    for(int i = LG - 1; i >= 0; i--){
        if(minjump[i][cur].second && minjump[i][cur].first <= h[block]){
            cur = minjump[i][cur].second;
            res += (1 << i);
        }
    }
    int kq = 1e9;
    if(cur == block) kq = min(kq, res);
    if(rpos != -1 && h[rpos] < h[peak]){
        int ans = 0;
        if(a <= rpos && rpos <= b) cur = rpos;
        else{
            cur = get(a, b).second;
            for(int i = LG - 1; i >= 0; i--){
                if(maxjump[i][cur].second && maxjump[i][cur].first <= h[rpos]){
                    cur = maxjump[i][cur].second;
                    ans += (1 << i);
                }
            }
            for(int i = LG - 1; i >= 0; i--){
                if(minjump[i][cur].second && minjump[i][cur].first <= h[rpos]){
                    cur = minjump[i][cur].second;
                    ans += (1 << i);
                }
            }
        }
        if(cur == rpos) kq = min(kq, ans);
    }

    if(kq == 1e9) return -1;
    else return kq + 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