Submission #1196977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196977		GoBananas69	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	0 ms	416 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];
int tree[maxn * 4];
vector<int> H;

void build(int id, int tl, int tr, vector<int> &h) {
    if(tl == tr) {
        tree[id] = h[tl];
        return;
    }
    int tm = (tl + tr) / 2;
    build(id * 2 + 1, tl, tm, h);
    build(id * 2 + 2, tm + 1, tr, h);
    tree[id] = max(tree[id * 2 + 1], tree[id * 2 + 2]);
}

int query(int id, int tl, int tr, int l, int r) {
    if(tl == l && r == tr) return tree[id];
    int tm = (tl + tr) / 2;
    if(r <= tm) return query(id * 2 + 1, tl, tm, l, r);
    if(tm < l) return query(id * 2 + 2, tm + 1, tr, l, r);
    int LQ = query(id * 2 + 1, tl, tm, l, tm);
    int RQ = query(id * 2 + 2, tm + 1, tr, tm + 1, r);
    return max(LQ, RQ);
}

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]);
        }
    }
    build(0, 0, n - 1, h);
    H = h;
}

int minimum_jumps(int A, int B, int C, int D) {
    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;
        if(A + 1 == C) return -1;
        int h = query(0, 0, n - 1, A + 1, C - 1);
        if(h > H[C]) return -1;
        return res + 1;
    }
    
    return -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