Submission #1125106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125106		SamueleVid	Rainforest Jumps (APIO21_jumps)	C++20	37 / 100	4085 ms	19392 KiB

jumps

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

int N;
vector<int> H;
vector<vector<int>> adj;
bool first_subtask = true;

constexpr ll PW = 262144;

struct segment {
    vector<ll> seg;
    segment() {
        seg.assign(2 * PW, 1e9);
    }

    void update(int x, ll d) {
        x += PW;
        seg[x] = d;
        x /= 2;
        while (x >= 1) {
            seg[x] = min(seg[2 * x], seg[2 * x + 1]);
            x /= 2;
        }
    }

    ll query(int l, int r) {
        l += PW; r += PW;
        ll sol = 1e9;
        while (l <= r) {
            if (l % 2 == 1) {
                sol = min(sol, seg[l]);
                l ++;
            }
            if (r % 2 == 0) {
                sol = min(sol, seg[r]);
                r --;
            }
            l /= 2; r /= 2;
        }
        return sol;
    }

    void clear() {
        for (int i = 0; i < 2 * PW; i ++) seg[i] = 1e9;
    }
};

segment seg;

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

    vector<int> inv_H(N + 1);
    for (int i = 0; i < N; i ++) inv_H[H[i]] = i;

    for (int i = 0; i < N; i ++) {
        if (H[i] != i + 1) first_subtask = false;
    }
    if (first_subtask) return;

    adj.resize(N);
    // a destra
    for (int i = N - 1; i >= 0; i --) {
        int u = seg.query(H[i] + 1, N);
        if (u != 1e9) adj[i].push_back(u);
        seg.update(H[i], i);
    }

    seg.clear();
    // a sinistra
    for (int i = 0; i < N; i ++) {
        int u = -seg.query(H[i] + 1, N);
        if (u != -1e9) adj[i].push_back(u);
        seg.update(H[i], -i);
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (first_subtask) return C - B;
    vector<int> v(N);
    vector<int> d(N, 1e9);
    queue<int> q;
    for (int i = A; i <= B; i ++) {
        q.push(i);
        d[i] = 0;
        v[i] = 1;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto x : adj[u]) {
            if (v[x]) continue;
            d[x] = d[u] + 1;
            v[x] = 1;
            q.push(x);
        }
    }

    int res = 1e9;
    for (int i = C; i <= D; i ++) res = min(res, d[i]);
    if (res == 1e9) res = -1;
    return res;
}

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