Submission #415724

#	Time	Username	Problem	Language	Result	Execution time	Memory
415724		valerikk	Rainforest Jumps (APIO21_jumps)	C++17	31 / 100	4083 ms	64400 KiB

jumps

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 2e5 + 7;
const int LG = 19;
const int INF = 1e9;

int n, h[N];
int go_l[N], go_r[N], go_mx[N];
int bin_l[LG][N], bin_r[LG][N], bin_mx[LG][N];
int lg[N];
int sparse[LG][N];

int get_max(int l, int r) {
    int t = lg[r - l];
    return max(sparse[t][l], sparse[t][r - (1 << t)]);
}

void build() {
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            go_r[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    go_r[n - 1] = n - 1;
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            go_l[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    go_l[0] = 0;
    for (int i = 0; i < n; ++i) {
        if (h[go_l[i]] > h[go_r[i]]) go_mx[i] = go_l[i]; else go_mx[i] = go_r[i];
    }
    for (int i = 0; i < n; ++i) {
        bin_l[0][i] = go_l[i];
        bin_r[0][i] = go_r[i];
        bin_mx[0][i] = go_mx[i];
        sparse[0][i] = h[i];
    }
    for (int t = 1; t < LG; ++t) {
        for (int i = 0; i < n; ++i) {
            bin_l[t][i] = bin_l[t - 1][bin_l[t - 1][i]];
            bin_r[t][i] = bin_r[t - 1][bin_r[t - 1][i]];
            bin_mx[t][i] = bin_mx[t - 1][bin_mx[t - 1][i]];
            if (i + (1 << t) <= n) sparse[t][i] = max(sparse[t - 1][i], sparse[t - 1][i + (1 << (t - 1))]);
        }
    }
    lg[0] = lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
}

void init(int n2, vector<int> h2) {
    for (int i = 1; i <= n2; ++i) h[i] = h2[i - 1] - 1;
    h[0] = n2;
    h[n2 + 1] = n2 + 1;
    n = n2 + 2;
    build();
}

int get_dist(int v, int t) {
    int d = 0;
    for (int i = LG - 1; i >= 0; --i) {
        if (h[bin_mx[i][v]] <= h[t]) {
            d += (1 << i);
            v = bin_mx[i][v];
        }
    }
    for (int i = LG - 1; i >= 0; --i) {
        if (h[bin_r[i][v]] <= h[t]) {
            d += (1 << i);
            v = bin_r[i][v];
        }
    }
    return v == t ? d : INF;
}

int minimum_jumps(int A, int B, int C, int D) {
    int a = A + 1, b = B + 2, c = C + 1, d = D + 2;
    int res = INF;
    for (int s = a; s < b; ++s) {
        for (int t = c; t < d; ++t) res = min(res, get_dist(s, t));
    }
    return res == INF ? -1 : res;
}

#ifdef LOCAL
int main() {
    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n2, q2;
    cin >> n2 >> q2;
    vector<int> h2(n2);
    for (auto &i : h2) cin >> i;
    init(n2, h2);
    while (q2--) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        cout << minimum_jumps(A, B, C, D) << endl;
    }
    return 0;
}
#endif

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