oj.uz

Submission #971435

# Submission time Handle Problem Language Result Execution time Memory
971435 2024-04-28T13:47:11 Z Pannda Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 96816 KB 
#include "jumps.h"

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

struct SegmentTree {
    struct Node {
        int sum = 0;
        int ln = 0, rn = 0;
    };

    int n;
    vector<Node> nodes;
    vector<int> roots;

    SegmentTree() {}
    SegmentTree(int n) : n(n), nodes(1), roots(1, 0) {}

    void add(int i, int delta, int base, int &idx, int l, int r) {
        idx = nodes.size();
        nodes.push_back(nodes[base]);
        nodes[idx].sum += delta;
        if (l + 1 < r) {
            int m = (l + r) >> 1;
            Node goat = nodes[idx];
            if (i < m) add(i, delta, nodes[base].ln, goat.ln, l, m);
            else add(i, delta, nodes[base].rn, goat.rn, m, r);
            nodes[idx] = goat;
        }
    }

    void add(int i, int val) {
        roots.emplace_back();
        add(i, val, roots.end()[-2], roots.end()[-1], 0, n);
    }

    int find(int ub, int idxl, int idxr) {
        auto dfs = [&](auto self, int idxl, int idxr, int l, int r) -> int {
            if (l >= ub) return -1;
            if (nodes[idxr].sum - nodes[idxl].sum == 0) return -1;
            if (l + 1 == r) return l;
            int m = (l + r) >> 1;
            int get = self(self, nodes[idxl].rn, nodes[idxr].rn, m, r);
            if (get != -1) return get;
            return self(self, nodes[idxl].ln, nodes[idxr].ln, l, m);
        };
        return dfs(dfs, idxl, idxr, 0, n);
    }
};


struct RMQ {
    static const int INF = 1e9 + 12345;
    int n, log;
    vector<vector<int>> mx;
    RMQ() {}
    RMQ(vector<int> a) : n(a.size()), log(32 - __builtin_clz(n)), mx(n, vector<int>(log, -INF)) {
        for (int i = n - 1; i >= 0; i--) {
            mx[i][0] = a[i];
            for (int k = 1; k < log; k++) {
                int j = i + (1 << (k - 1));
                mx[i][k] = max(mx[i][k - 1], j < n ? mx[j][k - 1] : -INF);
            }
        }
    }
    int getMax(int ql, int qr) {
        int k = 31 - __builtin_clz(qr - ql);
        return max(mx[ql][k], mx[qr - (1 << k)][k]);
    }
};

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

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;
    }
    rmq = RMQ(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];
        }
    }

    seg = SegmentTree(n + 1);
    for (int i = 0; i < n; i++) {
        seg.add(h[i], +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(h[to], seg.roots[l0], seg.roots[r0]);
        if (from == -1) continue;
        from = ih[from];
        if (rmq.getMax(from, to) > h[to]) continue;
        int cnt = 0;
        for (int k = LOG - 1; k >= 0; k--) {
            int next = f[from][k];
            if (depth[next] >= depth[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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Execution timed out 4040 ms 87664 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 120 ms 86784 KB Output is correct
6 Correct 191 ms 96664 KB Output is correct
7 Correct 68 ms 50068 KB Output is correct
8 Correct 175 ms 95480 KB Output is correct
9 Correct 20 ms 13976 KB Output is correct
10 Correct 190 ms 95880 KB Output is correct
11 Correct 138 ms 96816 KB Output is correct
12 Correct 146 ms 96284 KB Output is correct
13 Incorrect 126 ms 96628 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 203 ms 46604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 203 ms 46604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Execution timed out 4040 ms 87664 KB Time limit exceeded
4 Halted 0 ms 0 KB -