Submission #954883

#	Time	Username	Problem	Language	Result	Execution time	Memory
954883		Unforgettablepl	Rainforest Jumps (APIO21_jumps)	C++17	48 / 100	844 ms	95556 KiB

jumps

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

#define int long long

int L[200002][18];
int Left[200002][18];
int arr[200001];
int tree[524288];
int rarr[200001];
int R[200002][18];
int n;

void update(int k,int x){
    k+=262144;
    tree[k]=x;
    k/=2;
    while(k){
        tree[k]=max(tree[2*k],tree[2*k+1]);
        k/=2;
    }
}

int get(int a,int b){
    a+=262144;b+=262144;
    int ans = INT32_MIN;
    while(a<=b){
        if(a&1)ans=max(ans,tree[a++]);
        if(b%2==0)ans=max(ans,tree[b--]);
        a/=2;b/=2;
    }
    return ans;
}

void init(int32_t N, vector<int32_t> H) {
    n=N;
    for(int i=0;i<N;i++)arr[i]=H[i];
    for(int i=0;i<N;i++)update(i,arr[i]);
    for(int i=0;i<N;i++)rarr[arr[i]]=i;
    stack<int> q;
    for(int i=0;i<N;i++){
        while(!q.empty() and q.top()<arr[i])q.pop();
        if(!q.empty())Left[arr[i]][0]=L[arr[i]][0]=q.top();
        else Left[arr[i]][0]=L[arr[i]][0]=n+1;
        q.emplace(arr[i]);
    }
    while(!q.empty())q.pop();
    for(int i=N-1;i>=0;i--){
        while(!q.empty() and q.top()<arr[i])q.pop();
        if(!q.empty())R[arr[i]][0]=q.top();
        else R[arr[i]][0]=n+1;
        q.emplace(arr[i]);
    }
    for(int bit=0;bit<=17;bit++)Left[n+1][bit]=L[n+1][bit]=R[n+1][bit]=n+1;
    for(int i=1;i<=N;i++)if(L[i][0] > R[i][0])swap(L[i][0], R[i][0]);
    for(int bit=1;bit<=17;bit++){
        for(int i=1;i<=N;i++){
            R[i][bit] = R[R[i][bit - 1]][bit - 1];
        }
    }
    for(int bit=1;bit<=17;bit++){
        for(int i=1;i<=N;i++){
            L[i][bit] = L[L[i][bit - 1]][bit - 1];
        }
    }
    for(int bit=1;bit<=17;bit++){
        for(int i=1;i<=N;i++){
            Left[i][bit] = Left[Left[i][bit - 1]][bit - 1];
        }
    }
}

int getans(int base,int tar){
    int ans = 0;
    for(int jump=17;jump>=0;jump--){
        if(R[base][jump] <= tar) { base = R[base][jump]; ans+=(1 << jump);}
    }
    for(int jump=17;jump>=0;jump--){
        if(L[base][jump] <= tar) { base = L[base][jump]; ans+=(1 << jump);}
    }
    return base==tar ? ans : -1;
}

int32_t minimum_jumps(int32_t A, int32_t B, int32_t C, int32_t D) {
    int base = arr[B];
    int tar = arr[C];
    int limit = min(tar,get(A,B));
    for(int jump=17;jump>=0;jump--){
        if(Left[base][jump]<=limit)base=Left[base][jump];
    }
    return getans(base,tar);
}

//int32_t main() {
//    int32_t N, Q;
//    assert(2 == scanf("%d %d", &N, &Q));
//    std::vector<int32_t> H(N);
//    for (int32_t i = 0; i < N; ++i) {
//        assert(1 == scanf("%d", &H[i]));
//    }
//    init(N, H);
//
//    for (int32_t i = 0; i < Q; ++i) {
//        int32_t 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;
//}

• 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