Submission #1196973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196973		GoBananas69	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	325 ms	34344 KiB

jumps

#include <cassert>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

#include "jumps.h"
using namespace std;
vector<vector<int>> adj;

bool subtask1 = true;
const int maxk = 20;
const int maxn = 2e5;

int L[maxn][maxk];
int R[maxn][maxk];

void init(int n, vector<int> h) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < maxk; j++) {
            L[i][j] = n;
            R[i][j] = -1;
        }
    }

    vector<int> q;
    for (int i = 0; i < n; ++i) {
        if (h[i] != i + 1) subtask1 = false;
        while (!q.empty() && h[q.back()] < h[i]) {
            q.pop_back();
        }
        if (!q.empty()) {
            L[i][0] = q.back();
        }
        q.push_back(i);
    }
    q.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!q.empty() && h[q.back()] < h[i]) {
            q.pop_back();
        }
        if (!q.empty()) {
            R[i][0] = q.back();
        } 
        q.push_back(i);
    }

    for (int j = 1; j < maxk; j++) {
        for (int i = 0; i < n; i++) {
            int u = L[i][j - 1];
            int v = R[i][j - 1];
            R[i][j] = max(R[u][j - 1], R[v][j - 1]);
            L[i][j] = min(L[u][j - 1], L[v][j - 1]);
        }
    }
    
}

int minimum_jumps(int A, int B, int C, int D) {
    if (subtask1) {
        return C - B;
    }
    int n = adj.size();
    if (A == B && C == D) {
        int res = 0;
        int r = A, l = A;
        for (int j = maxk - 1; j >= 0; j--) {
            if (R[r][j] != -1 && R[r][j] < C) {
                r = R[r][j];
                res += (1 << j);
                l = L[l][j];
            }
        }
        if (R[r][0] == C) return res + 1;
        if (l != n && R[l][0] == C) return res + 1;
        return -1;
    }
    
    return -1;
}

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