Submission #795812

#	Time	Username	Problem	Language	Result	Execution time	Memory
795812		GusterGoose27	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1187 ms	40360 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
const int MAXB = 20;
typedef pair<int, int> pii;
int height[MAXN];
int great[MAXN][2];
int nxt[MAXN][MAXB];
int depth[MAXN];
int n;

int get_max(int i, int j) { // returns rightmost in case
    if (i == -1) return j;
    if (j == -1) return i;
    return height[i] > height[j] ? i : j;
}

class stree {
public:
    int lp, rp;
    stree *l = nullptr;
    stree *r = nullptr;
    int mx = 0;
    stree(int lv, int rv) {
        lp = lv;
        rp = rv;
        if (lp < rp) {
            int m = (lp+rp)/2;
            l = new stree(lp, m);
            r = new stree(m+1, rp);
            reupd();
        }
        else mx = lp;
    }
    void reupd() {
        mx = get_max(l->mx, r->mx);
    }
    int range_mx(int lv, int rv) {
        if (lp > rv || rp < lv) return -1;
        if (lp >= lv && rp <= rv) return mx;
        return get_max(l->range_mx(lv, rv), r->range_mx(lv, rv));
    }
    int right_mx(int lv, int rv, int v) { // rightmost pos in lv...rv st height[i] > v
        if (lp > rv || rp < lv || height[mx] < v) return -1;
        if (lp == rp) return lp;
        int rq = r->right_mx(lv, rv, v);
        return rq == -1 ? l->right_mx(lv, rv, v) : rq;
    }
};

stree *tree;

void init(int N, vector<int> H) {
    n = N;
    height[n] = MAXN;
    for (int i = 0; i < n; i++) height[i] = H[i];
    tree = new stree(0, n-1);
    vector<int> rvals;
    depth[n] = 0;
    rvals.push_back(n);
    for (int i = n-1; i >= 0; i--) {
        while (height[i] > height[rvals.back()]) rvals.pop_back();
        great[i][0] = rvals.back();
        depth[i] = 1+depth[rvals.back()];
        rvals.push_back(i);
    }
    rvals.clear();
    rvals.push_back(-1);
    for (int i = 0; i < n; i++) {
        while (rvals.size() > 1 && height[i] > height[rvals.back()]) rvals.pop_back();
        great[i][1] = rvals.back();
        rvals.push_back(i);
    }
    for (int i = 0; i < n; i++) {
        nxt[i][0] = i;
        if (great[i][0] < n) nxt[i][0] = get_max(great[i][0], nxt[i][0]);
        if (great[i][1] >= 0) nxt[i][0] = get_max(great[i][1], nxt[i][0]);
    }
    for (int j = 1; j < MAXB; j++) {
        for (int i = 0; i < n; i++) {
            nxt[i][j] = nxt[nxt[i][j-1]][j-1];
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    int rmx = height[tree->range_mx(c, d)];
    if (height[b] > rmx) return -1;
    if (c == b+1) {
        return 1;
    }
    int dpos = tree->range_mx(b+1, c-1);
    int div = height[dpos];
    if (div > rmx) return -1;
    int lmx = tree->range_mx(a, b);
    int lgreat = tree->right_mx(0, b, div);
    int s = lmx;
    if (lgreat >= a) {
        if (height[lgreat] < rmx) return 1;
        s = tree->range_mx(lgreat+1, b);
    }
    int mv = 0;
    for (int i = MAXB-1; i >= 0; i--) {
        if (height[nxt[s][i]] <= div) {
            s = nxt[s][i];
            mv += (1<<i);
        }
    }
    // now, we either go to the left or we go to the right
    if (height[s] == div) return 1+mv;
    assert(lgreat != -1);
    if (height[lgreat] < rmx) return 2+mv;
    return mv+1+depth[s]-depth[dpos];
}

• 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