Submission #1212407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212407		ProtonDecay314	Rainforest Jumps (APIO21_jumps)	C++20	48 / 100	816 ms	135888 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

/*
yeah i could've used a set... but

i'm just coding a segtree because vibes :D
*/
struct Tree {
    Tree *lt, *rt;
    int l, r;
    int mn1, mx1;

    Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), mn1(INF(int)), mx1(NINF(int)) {};

    void combine() {
        mn1 = min(lt->mn1, rt->mn1);
        mx1 = max(lt->mx1, rt->mx1);
    }

    void build(const vb& a) {
        if(l == r) {
            if(a[l]) {
                mn1 = mx1 = l;
            }
            return;
        }

        int m = (l + r) >> 1;

        lt = new Tree(l, m);
        rt = new Tree(m + 1, r);
        lt->build(a);
        rt->build(a);

        combine();
    }

    int qmin(int ql, int qr) {
        if(ql > r || qr < l) return INF(int);

        if(ql == l && qr == r) return mn1;

        int m = (l + r) >> 1;

        return min(lt->qmin(ql, min(qr, m)), rt->qmin(max(ql, m + 1), qr));
    }

    int qmax(int ql, int qr) {
        if(ql > r || qr < l) return NINF(int);

        if(ql == l && qr == r) return mx1;

        int m = (l + r) >> 1;

        return max(lt->qmax(ql, min(qr, m)), rt->qmax(max(ql, m + 1), qr));
    }

    void upd(int i, bool nv) {
        if(l == r) {
            if(nv) mn1 = mx1 = l;
            else {
                mn1 = INF(int);
                mx1 = NINF(int);
            }
            return;
        }

        int m = (l + r) >> 1;

        if(i <= m) lt->upd(i, nv);
        else rt->upd(i, nv);

        combine();
    }
};

struct MaxTree {
    MaxTree *lt, *rt;
    int l, r, v;

    MaxTree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(NINF(int)) {};

    void combine() {
        v = max(lt->v, rt->v);
    }

    void build(const vi& a) {
        if(l == r) {
            v = a[l];
            return;
        }

        int m = (l + r) >> 1;

        lt = new MaxTree(l, m);
        rt = new MaxTree(m + 1, r);

        lt->build(a);
        rt->build(a);

        combine();
    }

    int qry(int ql, int qr) {
        if(ql > r || qr < l) return NINF(int);

        if(ql == l && qr == r) return v;

        int m = (l + r) >> 1;

        return max(lt->qry(ql, min(qr, m)), rt->qry(max(ql, m + 1), qr));
    }
};

vi g_lptr;
vi g_rptr;

void print_vec(const vi& v) {
    for(int vv : v) cerr << vv << " ";
    cerr << endl;
}

struct PICK_STRATEGY {
    const static int HEAVY = 0, LIGHT = 1, LEFT = 2, RIGHT = 3;
};

const int MAX_JUMP = 20;

vvi compute_jump_pointers(const vi& lptr, const vi& rptr, const vpi& node_order, const vi& h, int strategy) {
    int n = lptr.size();
    vvi jump(n, vi(MAX_JUMP, -1));

    // Initialize jump pointers

    for(int i = 0; i < n; i++) {
        int next_ptr = -1;

        switch(strategy) {
            default:
            case PICK_STRATEGY::HEAVY:
                {
                    if(lptr[i] == NINF(int)) {
                        next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]);
                    } else if(rptr[i] == INF(int)) {
                        next_ptr = lptr[i];
                    } else if(h[lptr[i]] > h[rptr[i]]) {
                        next_ptr = lptr[i];
                    } else {
                        next_ptr = rptr[i];
                    }
                }
                break;
            case PICK_STRATEGY::LIGHT:
                {
                    if(lptr[i] == NINF(int)) {
                        next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]);
                    } else if(rptr[i] == INF(int)) {
                        next_ptr = lptr[i];
                    } else if(h[lptr[i]] > h[rptr[i]]) {
                        next_ptr = rptr[i];
                    } else {
                        next_ptr = lptr[i];
                    }
                }
                break;
            case PICK_STRATEGY::LEFT:
                {
                    next_ptr = (lptr[i] == NINF(int) ? -1 : lptr[i]);
                }
                break;
            case PICK_STRATEGY::RIGHT:
                {
                    next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]);
                }
                break;
        }

        jump[i][0] = next_ptr;
    }

    for(int i = 0; i < n; i++) {
        int ci = node_order[i].second;

        for(int j = 1; j < MAX_JUMP; j++) {
            if(jump[ci][j - 1] == -1) break;
            jump[ci][j] = jump[jump[ci][j - 1]][j - 1];
        }
    }

    return jump;
}

vvi heavy_ptrs;
vvi left_ptrs;
vvi right_ptrs;

MaxTree* g_tr;

vi g_h;

void init(int N, vi H) {
    // computing left/right pointers
    vpi h_ind_pairs_right_order;
    vpi h_ind_pairs_left_order;

    vi lptr(N, -1);
    vi rptr(N, -1);

    for(int i = 0 ; i < N; i++) {
        h_ind_pairs_right_order.pb({H[i], i});
        h_ind_pairs_left_order.pb({H[i], i});
    }

    sort(h_ind_pairs_right_order.begin(), h_ind_pairs_right_order.end(), [](pi a, pi b) {return a.first > b.first || (a.first == b.first && a.second < b.second);});
    sort(h_ind_pairs_left_order.begin(), h_ind_pairs_left_order.end(), [](pi a, pi b) {return a.first > b.first || (a.first == b.first && a.second > b.second);});

    Tree* tr_right = new Tree(0, N - 1);
    Tree* tr_left = new Tree(0, N - 1);

    vb all_false(N, false);

    tr_right->build(all_false);
    tr_left->build(all_false);

    for(int i = 0 ; i < N; i++) {
        rptr[h_ind_pairs_right_order[i].second] = tr_right->qmin(h_ind_pairs_right_order[i].second + 1, N - 1);
        lptr[h_ind_pairs_left_order[i].second] = tr_left->qmax(0, h_ind_pairs_left_order[i].second - 1);

        tr_right->upd(h_ind_pairs_right_order[i].second, true);
        tr_left->upd(h_ind_pairs_left_order[i].second, true);
    }

    g_lptr = lptr;
    g_rptr = rptr;

    /*
    computing jump pointers
    you will need:
    (1) heavy jump pointers
    (2) light jump pointers (nvm no need for this)
    (3) left jump pointers
    (4) right jump pointers
    */
    heavy_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::HEAVY);
    left_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::LEFT);
    right_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::RIGHT);

    g_tr = new MaxTree(0, N - 1);
    g_tr->build(H);
    g_h = H;
}

int p2p_minjumps(int s, int C) {
    int num_jumps = 0;

    int ci = s;

    // Jump along heavy edges
    for(int i = MAX_JUMP - 1; i >= 0; i--) {
        if(heavy_ptrs[ci][i] != -1 && g_h[heavy_ptrs[ci][i]] < g_h[C]) {
            // if we can jump, jump
            num_jumps |= 1 << i;
            ci = heavy_ptrs[ci][i];
        }
    }

    // Jump to the right
    for(int i = MAX_JUMP - 1; i >= 0; i--) {
        if(right_ptrs[ci][i] != -1 && right_ptrs[ci][i] < C) {
            // if we can jump, jump
            num_jumps += 1 << i;
            ci = right_ptrs[ci][i];
        }
    }

    return num_jumps + 1;
}

int minimum_jumps(int A, int B, int C, int D) {
    // Binary jumping

    // The idea is to find the optimal starting point in [A, B]

    // Move as far to the right as you possibly can (find the peak)
    int ce = C;

    for(int i = MAX_JUMP - 1; i >= 0; i--) {
        if(right_ptrs[ce][i] != -1 && right_ptrs[ce][i] <= D) {
            ce = right_ptrs[ce][i];
        }
    }

    if(g_tr->qry(B, ce - 1) >= g_h[ce]) return -1;

    // Move as far to the left as you possibly can 

    int cs = B;

    for(int i = MAX_JUMP - 1; i >= 0; i--) {
        if(left_ptrs[cs][i] != -1 && g_h[left_ptrs[cs][i]] < g_h[ce] && left_ptrs[cs][i] >= A) {
            cs = left_ptrs[cs][i];
        }
    }



    return p2p_minjumps(cs, C);
}

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