Submission #1071161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071161		stdfloat	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	870 ms	44896 KiB

jumps

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

vector<int> h;

vector<vector<int>> sp, spr;

void init(int n, vector<int> H) {
    h = H;

    stack<int> s;
    vector<int> l(n);
    // cout << "\nL\n";
    for (int i = 0; i < n; i++) {
        while (!s.empty() && h[s.top()] < h[i]) s.pop();

        l[i] = (s.empty() ? -1 : s.top());
        s.push(i);

        // cout << "i " << i << ' ' << l[i] << '\n';
    }

    while (!s.empty()) s.pop();

    sp.assign(n, vector<int>(17, -1)); spr = sp;
    // cout << "\nR\n";
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && h[i] > h[s.top()]) s.pop();

        // cout << "i " << i << ' ' << (s.empty() ? -1 : s.top()) << '\n';

        if (s.empty()) sp[i][0] = l[i];
        else {
            sp[i][0] = (l[i] == -1 || h[l[i]] < h[s.top()] ? s.top() : l[i]);
            spr[i][0] = s.top();
        }
    
        s.push(i);
    }

    for (int i = 1; i < 17; i++) {
        for (int j = 0; j < n; j++) {
            if (sp[j][i - 1] != -1) sp[j][i] = sp[sp[j][i - 1]][i - 1];
            if (spr[j][i - 1] != -1) spr[j][i] = spr[spr[j][i - 1]][i - 1];
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    // cout << "\nQ " << a << ' ' << b << ' ' << c << ' ' << d << endl;

    int cnt = 0;
    for (int i = 16; i >= 0; i--) {
        // cout << "i " << i << ' ' << sp[a][i] << ' ' << (sp[a][i] == -1 ? -1 : h[sp[a][i]]) << ' ' << cnt << ' ' << a << endl;
        if (sp[a][i] != -1 && h[sp[a][i]] < h[c]) {
            cnt += (1 << i);
            a = sp[a][i];
        }
    }

    // cout << "cnt " << cnt << ' ' << a << endl;

    for (int i = 16; i >= 0; i--) {
        if (spr[a][i] != -1 && h[spr[a][i]] < h[c]) {
            cnt += (1 << i);
            a = spr[a][i];
        }
    }

    // cout << "cnt " << cnt << ' ' << a << ' ' << spr[a][0] << endl;

    return (spr[a][0] == c ? cnt + 1 : -1);
}

• 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