Submission #1212812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212812		kaltspielerhy	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	0 ms	444 KiB

jumps

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

struct direction {
    int gauche, droite;
};

int N;
vector<int> hauteurs;
vector<vector<direction>> plusCourt;

int minimum_jumps(int A, int B, int C, int D) {
    int result = 0;
    A++; B++; C++; D++;
    
    if (A < C) {
        int bitAct = 17;

        while (bitAct >= 0) {
            while (plusCourt[A][bitAct].droite == 0 || plusCourt[A][bitAct].droite > hauteurs[C-1]) {
                bitAct--;
            }
            if (bitAct >= 0) {
                A = plusCourt[A][bitAct].droite;
                result += (1 << bitAct);
            }
        }
    }
    else {
        int bitAct = 17;

        while (bitAct >= 0) {
            while (plusCourt[A][bitAct].gauche == 0 || plusCourt[A][bitAct].gauche > hauteurs[C-1]) {
                bitAct--;
            }
            if (bitAct >= 0) {
                A = plusCourt[A][bitAct].gauche;
                result += (1 << bitAct);
            }
        }
    }

    if (A != C) return -1;

    return result;
}

void init(int _N, vector<int> H) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    N = _N;
    hauteurs.resize(N);

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

    plusCourt.resize(N+1, vector<direction>(18, {0, 0}));

    vector<direction> parents(N+1, {0, 0});

    vector<pair<int, int>> parentDroite;
    parentDroite.push_back({hauteurs[0], 0});
    for (int i = 1; i < N; i++) {
        while (!parentDroite.empty() && hauteurs[i] > parentDroite.back().first) {
            parents[parentDroite.back().second+1].droite = i+1;
            cout << parentDroite.back().second+1 << " -> " << i+1 << '\n';
            parentDroite.pop_back();
        }

        parentDroite.push_back({hauteurs[i], i});
    }
    vector<pair<int, int>> parentGauche;
    parentGauche.push_back({hauteurs[N-1], N-1});
    for (int i = N-2; i >= 0; i--) {
        while (!parentGauche.empty() && hauteurs[i] > parentGauche.back().first) {
            parents[parentGauche.back().second+1].gauche = i+1;
            cout << parentGauche.back().second+1 << " -> " << i+1 << '\n';
            parentGauche.pop_back();
        }

        parentGauche.push_back({hauteurs[i], i});
    }

    for (int iNoeud = 1; iNoeud <= N; iNoeud++) {
        plusCourt[iNoeud][0] = {parents[iNoeud].gauche, parents[iNoeud].droite};
    }

    for (int iBit = 1; iBit < 18; iBit++) {
        for (int iNoeud = 1; iNoeud <= N; iNoeud++) {
            plusCourt[iNoeud][iBit].gauche = max(plusCourt[plusCourt[iNoeud][iBit-1].gauche][iBit-1].gauche,
                                                 plusCourt[plusCourt[iNoeud][iBit-1].droite][iBit-1].gauche);
            plusCourt[iNoeud][iBit].droite = max(plusCourt[plusCourt[iNoeud][iBit-1].gauche][iBit-1].droite,
                                                 plusCourt[plusCourt[iNoeud][iBit-1].droite][iBit-1].droite);                                  
        }
    }
}

// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int Q;
//     cin >> N >> Q;

//     int* H_array = new int[N];
//     for (int i = 0; i < N; i++) cin >> H_array[i];

//     init(N, H_array);

//     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";
//     }

//     delete[] H_array;
//     return 0;
// }

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