제출 #415736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415736		valerikk	밀림 점프 (APIO21_jumps)	C++17	48 / 100	1951 ms	64412 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) {
    if (l >= r) return -INF;
    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 minimum_jumps(int A, int B, int C, int D) {
    int a = A + 1, b = B + 2, c = C + 1, d = D + 2;
    int mx = get_max(c, d);
    int v = b - 1;
    for (int i = LG - 1; i >= 0; --i) {
        if (bin_l[i][v] >= a && h[bin_l[i][v]] < mx) v = bin_l[i][v];
    }
    int mx2 = get_max(b, c);
    int res = 0;
    for (int i = LG - 1; i >= 0; --i) {
        if (h[bin_mx[i][v]] < mx2) {
            res += (1 << i);
            v = bin_mx[i][v];
        }
    }
    if (h[go_mx[v]] >= mx2 && h[go_mx[v]] <= mx) {
        ++res;
        v = go_mx[v];
    }
    for (int i = LG - 1; i >= 0; --i) {
        if (bin_r[i][v] < c) {
            v = bin_r[i][v];
            res += (1 << i);
        }
    }
    if (v >= c && v < d) return res;
    if (go_r[v] >= c && go_r[v] < d) return res + 1;
    return -1;
}

#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: 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