Submission #882921

#	Time	Username	Problem	Language	Result	Execution time	Memory
882921		salmon	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	955 ms	79724 KiB

jumps

#include "jumps.h"

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

int parent[200100][31];
int l[200100][31];
int r[200100][31];
int N;
vector<int> v;
vector<int> proc;
int st[200100 * 4];

void build(int i, int s, int e){
    if(s != e){
        int m = (s + e)/2;
        build(i * 2, s,m);
        build(i * 2 + 1, m + 1, e);
        st[i] = max(st[i * 2],st[i * 2 + 1]);
    }
    else{
        st[i] = v[s];
    }
}

int query(int i, int s ,int e, int S, int E){
    if(E < S) return 0;
    if(S <= s && e <= E){
        return st[i];
    }

    int m = (s + e)/2;

    if(E <= m){
        return query(i * 2, s,m, S,E);
    }
    if(m < S){
        return query(i * 2 + 1, m + 1, e,S,E);
    }

    return max(query(i * 2, s,m, S,E),query(i * 2 + 1, m + 1, e,S,E));
}

void init(int n, std::vector<int> H) {
    N = n;
    v = H;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < 30; j++){
            l[i][j] = -1;
            r[i][j] = -1;
            parent[i][j] = -1;
        }
    }

    for(int i = 0; i < N; i++){
        while(!proc.empty() && v[proc.back()] < v[i]){
            r[proc.back()][0] = i;
            proc.pop_back();
        }

        proc.push_back(i);
    }

    proc.clear();

    for(int i = N - 1; i > -1; i--){
        while(!proc.empty() && v[proc.back()] < v[i]){
            l[proc.back()][0] = i;
            proc.pop_back();
        }

        proc.push_back(i);
    }

    proc.clear();

    for(int i = 0; i < N; i++){
        if(l[i][0] != -1){
            parent[i][0] = l[i][0];
        }
        if(r[i][0] != -1 && (v[r[i][0]] > v[l[i][0]] || parent[i][0] == -1)){
            parent[i][0] = r[i][0];
        }
    }

    for(int j = 1; j < 30; j++){
        for(int i = 0; i < N; i++){
            if(l[i][j - 1] != -1){
                l[i][j] = l[l[i][j - 1]][j - 1];
            }

            if(r[i][j - 1] != -1){
                r[i][j] = r[r[i][j - 1]][j - 1];
            }

            if(parent[i][j - 1] != -1){
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }

        }
    }

    build(1,0,N-1);
}

int minimum_jumps(int A, int B, int C, int D) {
    int steps = 0;


    if(query(1,0,N - 1, B + 1, C - 1) > query(1,0,N-1,C,D)){
        return -1;
    }

    int m = query(1,0,N-1,C,D);
    int m1;

    int h = B;
    for(int i = 25; i > -1; i--){
        if(l[h][i] == -1) continue;
        if(l[h][i] >= A && v[l[h][i]] < m){
            h = l[h][i];
        }
    }

    if(v[h] > m){
        return -1;
    }

    m1 = query(1,0,N - 1, B + 1, C - 1);

    for(int i = 25; i > -1; i--){
        if(parent[h][i] == -1) continue;
        if(v[parent[h][i]] <= m1){
            h = parent[h][i];
            steps += (1<<i);
        }
    }

    //printf("%d\n",r[h][0]);

    if(v[r[h][0]] > m1){
        return steps + 1;
    }
    if(parent[h][0] != -1 && v[parent[h][0]] <= m){
        return steps + 2;
    }

    for(int i = 25; i > -1; i--){
        if(r[h][i] == -1) continue;
        if(r[h][i] < C){
            h = r[h][i];
            steps += (1<<i);
        }
    }


    return steps + 1;
}

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