Submission #1137745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137745		adaawf	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	512 ms	88916 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
int n, a[200005], p[200005][2][18], ll[200005];
pair<int, int> l[200005][18], pp[200005][18];
void init(int N, vector<int> aa) {
    n = N;
    for (int i = 1; i <= n; i++) {
        a[i] = aa[i - 1];
    }
    for (int i = 2; i <= n; i++) ll[i] = ll[i / 2] + 1;
    a[0] = a[n + 1] = 1e9;
    stack<int> s;
    for (int i = 1; i <= n; i++) {
        while (!s.empty() && a[s.top()] <= a[i]) s.pop();
        if (s.empty()) p[i][0][0] = 0;
        else p[i][0][0] = s.top();
        s.push(i);
        pp[i][0] = {a[i], i};
    }
    while (!s.empty()) s.pop();
    for (int i = n; i >= 1; i--) {
        while (!s.empty() && a[s.top()] <= a[i]) s.pop();
        if (s.empty()) p[i][1][0] = n + 1;
        else p[i][1][0] = s.top();
        int h = p[i][0][0], k = p[i][1][0];
        if (a[h] > a[k]) l[i][0] = {a[h], h};
        else l[i][0] = {a[k], k};
        s.push(i);
    }
    p[n + 1][0][0] = p[n + 1][1][0] = n + 1;
    l[0][0] = {a[0], 0}; l[n + 1][0] = {a[n + 1], n + 1};
    for (int i = 1; i <= 17; i++) {
        for (int j = 0; j <= n + 1; j++) {
            p[j][0][i] = p[p[j][0][i - 1]][0][i - 1];
            p[j][1][i] = p[p[j][1][i - 1]][1][i - 1];
        }
        for (int j = 0; j <= n + 1; j++) {
            l[j][i] = l[l[j][i - 1].second][i - 1];
        }
        for (int j = 1; j <= n - (1 << i) + 1; j++) {
            pp[j][i] = max(pp[j][i - 1], pp[j + (1 << (i - 1))][i - 1]);
        }
    }
}
int travel(int x, int y) {
    if (a[y] < a[x]) return 1e9;
    int c = 0;
    for (int i = 17; i >= 0; i--) {
        if (l[x][i].first > a[y]) continue;
        x = l[x][i].second;
        c += (1 << i);
    }
    if (x < y) {
        for (int i = 17; i >= 0; i--) {
            int h = p[x][1][i];
            if (a[h] > a[y]) continue;
            x = h;
            c += (1 << i);
        }
    }
    else {
        for (int i = 17; i >= 0; i--) {
            int h = p[x][0][i];
            if (a[h] > a[y]) continue;
            x = h;
            c += (1 << i);
        }
    }
    return c;
}
pair<int, int> trya(int x, int y) {
    if (x > y) return {0, 0};
    int h = ll[y - x + 1];
    return max(pp[x][h], pp[y - (1 << h) + 1][h]);
}
int minimum_jumps(int x, int y, int z, int t) {
    x++; y++; z++; t++;
    pair<int, int> hh = trya(y + 1, z - 1), u = trya(x, y);
    int mi = 1e9;
    if (u.first > hh.first) {
        int l = u.second, r = y, res = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (trya(mid, y).first >= hh.first) {
                res = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        int h = res;
        h = p[h][1][0];
        if (z <= h && h <= t) return 1;
    }
    if (u.second != y) {
        if (z <= p[hh.second][1][0] && p[hh.second][1][0] <= t) {
            int l = u.second + 1, r = y, res = 0;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (trya(mid, y).first < hh.first) {
                    res = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            if (res != 0) {
                int h = trya(res, y).second;
                mi = min(mi, travel(h, hh.second) + 1);
            }
        }
    }
    int h = u.second;
    for (int i = 17; i >= 0; i--) {
        if (a[p[h][0][i]] >= hh.first) continue;
        h = p[h][0][i];
    }
    h = p[h][0][0];
    if (h != 0) {
        if (z <= p[h][1][0] && p[h][1][0] <= t) {
            mi = min(mi, travel(u.second, h) + 1);
        }
    }
    if (z <= p[hh.second][1][0] && p[hh.second][1][0] <= t) {
        mi = min(mi, travel(u.second, hh.second) + 1);
    }
    if (mi == 1e9) return -1;
    return mi;
}

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