Submission #981599

#	Time	Username	Problem	Language	Result	Execution time	Memory
981599		Ghulam_Junaid	Rainforest Jumps (APIO21_jumps)	C++17	81 / 100	4050 ms	570704 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"

using namespace std;

const int MXN = 2e5 + 10;
const int T = 330;

int n, pos[MXN], to_left[MXN], to_right[MXN], dp[MXN][T + 1], dp_right[MXN][T + 1];
vector<int> seg[4 * MXN], h;
bool subtask1 = 1;

void build(int v = 1, int s = 0, int e = n){
    if (e - s == 1){
        seg[v] = {h[s]};
        return;
    }

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    build(lc, s, mid);
    build(rc, mid, e);

    seg[v] = seg[lc];
    for (int x : seg[rc])
        seg[v].push_back(x);

    sort(seg[v].begin(), seg[v].end());
}

int get(int l, int r, int x, int v = 1, int s = 0, int e = n){
    // int mx = -1;
    // for (int i = l; i < r; i ++)
    //     if (h[i] < x)
    //         mx = max(mx, h[i]);
    // return mx;

    if (e <= l || r <= s) return -1;
    if (l <= s && e <= r){
        if (x > seg[v].back())
            return seg[v].back();
        if (x <= seg[v][0])
            return -1;

        int lb = lower_bound(seg[v].begin(), seg[v].end(), x) - seg[v].begin();
        return seg[v][lb - 1];
    }

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    return max(get(l, r, x, lc, s, mid), get(l, r, x, rc, mid, e));
}

void init(int N, vector<int> H) {
    n = N;
    h = H;

    for (int i = 0; i < n; i ++)
        pos[h[i]] = i, subtask1 &= (h[i] == (i + 1));

    build();

    stack<int> S;
    for (int i = 0; i < n; i ++){
        while(S.size() and h[S.top()] <= h[i])
            S.pop();

        if (S.size())
            to_left[i] = S.top();
        else
            to_left[i] = i;
        
        S.push(i);
    }

    while (S.size())
        S.pop();

    for (int i = n - 1; i >= 0; i --){
        while (S.size() and h[S.top()] <= h[i])
            S.pop();

        if (S.size())
            to_right[i] = S.top();
        else
            to_right[i] = i;

        S.push(i);
    }

    // for (int i = 0; i < n; i ++){
    //     to_left[i] = to_right[i] = i;
    //     for (int j = i + 1; j < n; j ++){
    //         if (h[j] > h[i]){
    //             to_right[i] = j;
    //             break;
    //         }
    //     }
    //     for (int j = i - 1; j >= 0; j --){
    //         if (h[j] > h[i]){
    //             to_left[i] = j;
    //             break;
    //         }
    //     }
    // }

    for (int i = 0; i < n; i ++){
        dp[i][0] = i;
        dp_right[i][0] = i;
        for (int j = 1; j <= T; j ++){
            dp[i][j] = (h[to_left[dp[i][j - 1]]] > h[to_right[dp[i][j - 1]]]) ? to_left[dp[i][j - 1]] : to_right[dp[i][j - 1]];
            dp_right[i][j] = to_right[dp_right[i][j - 1]];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (subtask1) return C - B;

    B++, D++;

    int mx = get(C, D, n + 1);
    
    int l = A - 1, r = B - 1;
    if (get(r, C, n + 1) > mx)
        return -1;
    while (r - l > 1){
        int mid = (l + r) / 2;
        if (get(mid, C, n + 1) > mx)
            l = mid;
        else
            r = mid;
    }

    int val = get(r, B, mx);

    if (val == -1)
        return -1;

    int st = pos[val];
    if (get(st, C, n + 1) > mx) return -1;

    int ope = 0;

    if (C + 1 == D){
        while (h[dp[st][T]] < h[C]){
            st = dp[st][T];
            ope += T;
        }
        for (int i = 1; i < T; i ++){
            if (h[dp[st][T - i]] < h[C]){
                st = dp[st][T - i];
                ope += T - i;
                break;
            }
        }

        while (h[dp_right[st][T]] < h[C]){
            st = dp_right[st][T];
            ope += T;
        }

        for (int i = 1; i <= T; i ++){
            if (h[dp_right[st][i]] == h[C]){
                ope += i;
                break;
            }
        }
    }
    else{
        while (st < C){
            ope++;
            int opt1 = to_left[st];
            int opt2 = to_right[st];

            if (opt2 >= C or h[opt2] > h[opt1] or h[opt1] > mx)
                st = opt2;
            else
                st = opt1;
        }
    }

    return ope;
}

• 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: 0 / 19