제출 #1118848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118848		Zero_OP	밀림 점프 (APIO21_jumps)	C++14	44 / 100	2253 ms	58968 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 5;
const int inf = 1e9;

int N, L, H[MAX], next_left[20][MAX], next_right[20][MAX], next_greater[20][MAX];
int rmq_id[20][MAX];

int combine(int i, int j){
    return (H[i] < H[j] ? j : i);
}

void init(int _N, vector<int> _H){
    N = _N;
    for(int i = 0; i < N; ++i) H[i] = _H[i];

    stack<int> st;
    for(int i = 0; i < N; ++i){
        while(!st.empty() && H[st.top()] <= H[i]) st.pop();
        if(!st.empty()) {
            next_left[0][i] = st.top();
        } else next_left[0][i] = -1;
        st.push(i);
    }

    stack<int>().swap(st);
    for(int i = N - 1; i >= 0; --i){
        while(!st.empty() && H[st.top()] <= H[i]) st.pop();
        if(!st.empty()) {
            next_right[0][i] = st.top();
        } else next_right[0][i] = -1;
        st.push(i);
    }

    for(int i = 0; i < N; ++i){
        if(next_left[0][i] == -1 && next_right[0][i] == -1) next_greater[0][i] = -1;
        else if(next_left[0][i] == -1) next_greater[0][i] = next_right[0][i];
        else if(next_right[0][i] == -1) next_greater[0][i] = next_left[0][i];
        else next_greater[0][i] = (H[next_left[0][i]] < H[next_right[0][i]] ? next_right[0][i] : next_left[0][i]);
    }

    for(int i = 0; i < N; ++i){
        rmq_id[0][i] = i;
    }

    #define refine(a, i, j) a[i][j] = (a[i - 1][j] == -1 ? -1 : a[i - 1][a[i - 1][j]])

    L = 32 - __builtin_clz(N);
    for(int i = 1; i < L; ++i){
        for(int j = 0; j < N; ++j){
            refine(next_left, i, j);
            refine(next_right, i, j);
            refine(next_greater, i, j);
            if(j + (1 << i) <= N){
                rmq_id[i][j] = combine(rmq_id[i - 1][j], rmq_id[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
}

int get_id(int l, int r){
    int k = 31 - __builtin_clz(r - l + 1);
    return combine(rmq_id[k][l], rmq_id[k][r - (1 << k) + 1]);
}

int solve(int s, int t){
    if(H[s] > H[t]) return -1;

    int ans = 0;
    for(int i = L - 1; i >= 0; --i){
        if(next_greater[i][s] != -1 && H[next_greater[i][s]] < H[t]){
            ans += (1 << i);
            s = next_greater[i][s];
        }
    }

    for(int i = L - 1; i >= 0; --i){
        if(next_right[i][s] != -1 && H[next_right[i][s]] < H[t]){
            ans += (1 << i);
            s = next_right[i][s];
        }
    }

    if(H[next_right[0][s]] != H[t]) return -1;
    ++ans;

    return ans;
}


int solve_2(int s, int l, int r, int id){ //only fixed start
    int ans = 0;

//    cout << "after phase 1 : " << s << ' ' << ans << '\n';

    for(int i = L - 1; i >= 0; --i){
        if(next_right[i][s] != -1 && next_right[i][s] < l){
            ans += (1 << i);
            s = next_right[i][s];
        }
    }

//    cout << "after phase 2 : " << s << ' ' << ans << '\n';

    if(next_right[0][s] == -1 || next_right[0][s] > r) return -1;
    ++ans;
    return ans;
}

int minimum_jumps(int a, int b, int c, int d){
    int s = b;
    int id = get_id(c, d);
    for(int i = L - 1; i >= 0; --i){
        if(next_left[i][s] != -1 && next_left[i][s] >= a && H[next_left[i][s]] <= H[id]){
            s = next_left[i][s];
        }
    }

    return solve(s, id);
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    int N, Q;
    cin >> N >> Q;

    vector<int> H(N);
    for(int i = 0; i < N; ++i){
        cin >> H[i];
    }

    init(N, H);

    for(int i = 0; i < Q; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d) << '\n';
    }

    return 0;
}
#endif //LOCAL

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