Submission #971464

#	Time	Username	Problem	Language	Result	Execution time	Memory
971464		Pannda	Rainforest Jumps (APIO21_jumps)	C++17	77 / 100	4032 ms	32856 KiB

jumps

#include "jumps.h"

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

struct SegmentTree {
    int n;
    vector<int> mx;
    vector<int> mn;

    SegmentTree() {}
    SegmentTree(vector<int> a) : n(a.size()), mx(4 * n), mn(4 * n) {
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (l + 1 == r) {
                mn[idx] = mx[idx] = a[l];
            } else {
                int m = (l + r) >> 1;
                self(self, 2 * idx + 1, l, m);
                self(self, 2 * idx + 2, m, r);
                mn[idx] = min(mn[2 * idx + 1], mn[2 * idx + 2]);
                mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
            }
        };
        dfs(dfs, 0, 0, n);
    }

    int find(int ql, int qr, int ub, int rb) {
        auto walk = [&](auto self, int idx, int l, int r) -> int {
            if (rb <= l) return -1;
            if (mx[idx] < ub) return -1;
            if (l + 1 == r) {
                return l;
            }
            int m = (l + r) >> 1;
            int get = self(self, 2 * idx + 2, m, r);
            if (get != -1) return get;
            return self(self, 2 * idx + 1, l, m);
        };
        int get = walk(walk, 0, 0, n);
        ql = max(ql, get + 1);
        if (ql >= qr) return -1;
        auto dfs = [&](auto self, int idx, int l, int r) -> int {
            if (r <= ql || qr <= l) return -1;
            if (ql <= l && r <= qr) return mx[idx];
            int m = (l + r) >> 1;
            return max(self(self, 2 * idx + 1, l, m), self(self, 2 * idx + 2, m, r));
        };
        return dfs(dfs, 0, 0, n);
    }

};

const int LOG = 17;
int n;
vector<int> h, ih;
SegmentTree seg;
vector<vector<int>> f;
vector<int> depth;

void init(int N, vector<int> H) {
    n = N;
    h = H;
    ih = vector<int>(n);
    for (int i = 0; i < n; i++) {
        h[i]--;
        ih[h[i]] = i;
    }
    seg = SegmentTree(h);
    h.push_back(n);
    f = vector<vector<int>>(n + 1, vector<int>(LOG, n));
    depth = vector<int>(n + 1, 0);

    vector<int> stk = { n };
    for (int i = n - 1; i >= 0; i--) {
        while (h[stk.back()] < h[i]) stk.pop_back();
        depth[i] = depth[stk.back()] + 1;
        f[i][0] = stk.back();
        stk.push_back(i);
    }

    stk.clear();
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && h[stk.back()] < h[i]) stk.pop_back();
        if (!stk.empty() && depth[stk.back()] <= depth[f[i][0]]) {
            f[i][0] = stk.back();
        }
        stk.push_back(i);
    }

    for (int k = 1; k < LOG; k++) {
        for (int i = 0; i < n; i++) {
            f[i][k] = f[f[i][k - 1]][k - 1];
        }
    }
}

int minimum_jumps(int l0, int r0, int l1, int r1) {
    r0++; r1++;
    int res = n;
    for (int to = l1; to < r1; to++) {
        int from = seg.find(l0, r0, h[to], to);
        if (from == -1) continue;
        from = ih[from];
        int cnt = 0;
        for (int k = LOG - 1; k >= 0; k--) {
            int next = f[from][k];
            if (depth[next] >= depth[to] && h[next] < h[to]) {
                from = next;
                cnt += 1 << k;
            }
        }
        res = min(res, cnt + depth[from] - depth[to]);
    }
    if (res == n) return -1;
    return res;
}

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