Submission #1137948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137948		ConquerConquerer	Rainforest Jumps (APIO21_jumps)	C++20	48 / 100	3325 ms	45852 KiB

jumps

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

const int maxN = 2e5 + 5;
int n;
vector<int> H;
int L[20][maxN], R[20][maxN], jump[20][maxN];

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

    H.insert(H.begin(), 1e9 + 1);
    H.insert(H.end(), 1e9 + 1);

    stack<int> st; st.push(0);
    for (int i = 1; i <= n; i++) {
        while (H[i] > H[st.top()]) st.pop();
        L[0][i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();
    st.push(n + 1);
    for (int i = n; i >= 1; i--) {
        while (H[i] > H[st.top()]) st.pop();
        R[0][i] = st.top();
        st.push(i);
    }

    L[0][0] = L[0][n + 1] = 0;
    R[0][0] = R[0][n + 1] = n + 1;
    for (int i = 0; i <= n + 1; i++)
        if (H[L[0][i]] > H[R[0][i]]) jump[0][i] = L[0][i];
            else jump[0][i] = R[0][i];

    //for (int i = 1; i <= n; i++)
        //cout << L[0][i] << ' ' << R[0][i] << ' ' << jump[0][i] << '\n';

    for (int k = 1; k <= 17; k++)
        for (int i = 1; i <= n; i++) {
            L[k][i] = L[k - 1][L[k - 1][i]];
            R[k][i] = R[k - 1][R[k - 1][i]];
            jump[k][i] = jump[k - 1][jump[k - 1][i]];
        }
}

int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;

    if (H[B] > H[C]) return -1;

    int pos = B;
    for (int i = B - 1; i >= A; i--) {
        if (H[i] > H[C]) break;
        if (H[i] > H[pos]) pos = i;
    }

    B = pos;

    int res = 0;
    for (int k = 17; k >= 0; k--) {
        if (H[jump[k][B]] <= H[C]) {
            res += (1 << k);
            B = jump[k][B];
        }
    }

    if (B == C) return res;

    if (H[R[0][B]] > H[C]) {
        for (int k = 17; k >= 0; k--)
            if (H[L[k][B]] <= H[C]) {
                res += (1 << k);
                B = L[k][B];
            }
    }
    else {
        for (int k = 17; k >= 0; k--)
            if (H[R[k][B]] <= H[C]) {
                res += (1 << k);
                B = R[k][B];
            }
    }

    if (B == C) return res;
    return -1;
}

/*

int main() {
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int A, B, C, D;
    assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
    printf("%d\n", minimum_jumps(A, B, C, D));
  }
  return 0;
}*/

/*
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
*/

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 0 / 19