Submission #1212216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212216		ProtonDecay314	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4034 ms	45836 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();
    }
};

vi g_lptr;
vi g_rptr;

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

void init(int N, vi H) {
    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(0, N - 1);
    Tree tr_left(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;

    // print_vec(lptr);
    // print_vec(rptr);
}

int minimum_jumps(int A, int B, int C, int D) {
    // BFS bruteforce

    queue<pi> q;

    int ans = -1;

    for(int i = A; i <= B; i++) {
        q.push({i, 0});
    }

    int n = g_lptr.size();

    vb vis(n, false);

    while(!q.empty()) {
        auto [i, cd] = q.front();

        q.pop();
        
        if(i < 0 || i >= n) continue;
        if(vis[i]) continue;
        vis[i] = true;

        if(C <= i && i <= D) {
            ans = cd;
            break;
        }

        q.push({g_lptr[i], cd + 1});
        q.push({g_rptr[i], cd + 1});
    }

    return ans;
}

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