Submission #1204064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204064		jasonic	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4100 ms	42308 KiB

jumps

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

int n;
int l[200005];
int r[200005];

struct Element{
    int idx, val;

    Element(): val(-1), idx(-1) {};
    Element(int a, int b): val(a), idx(b) {};

    bool operator<(const Element &b) const {
        return val < b.val;
    }

    bool operator>(const Element &b) const {
        return val > b.val;
    }
};

struct SegTree{
    int l, r;
    int mn, mx;
    Element maxEl;
    SegTree *lt, *rt;

    void comb() {
        mn = min(lt->mn, rt->mn);
        mx = max(lt->mx, rt->mx);
        maxEl = max(lt->maxEl, rt->maxEl);
    }

    SegTree(): l(0), r(0), mn(0), mx(0), lt(nullptr), rt(nullptr) {};
    
    SegTree(int bl, int br, vector<Element> &a) {
        l = bl; r = br;
        lt = rt = nullptr;
        mx = -1;
        mn = n;

        if(l == r) {
            maxEl = a[l];
        } else {
            int m = l + (r-l)/2;
            lt = new SegTree(l, m, a);
            rt = new SegTree(m+1, r, a);
            comb();
        }
    }

    void upd(int i) {
        if(i < l || r < i) return;
        if(i == l && l == r) {
            mn = mx = i;
        } else {
            lt->upd(i);
            rt->upd(i);
            comb();
        }
    }

    int qryMx(int ql, int qr) {
        if(qr < l || r < ql) return -1;
        if(ql <= l && r <= qr) return mx;
        else return max(lt->qryMx(ql, qr), rt->qryMx(ql, qr));
    }

    int qryMn(int ql, int qr) {
        if(qr < l || r < ql) return n;
        if(ql <= l && r <= qr) return mn;
        else return min(lt->qryMn(ql, qr), rt->qryMn(ql, qr));
    }

    Element starting(int ql, int qr) {
        if(qr < l || r < ql) return Element();
        if(ql <= l && r <= qr) return maxEl;
        else return max(lt->starting(ql, qr), rt->starting(ql, qr));
    }
};

SegTree segtree;
unordered_map<int, vector<int>> adjList;

void connect(int x, int y) {
    adjList[x].push_back(y);
}

void init(int N, vector<int> h) {
    n = N;
    set<int> process_idx;
    vector<Element> a;
    for(int i = 0; i < n; i++) {
        a.push_back(Element(h[i], i));
    }
    segtree = SegTree(0, n-1, a);

    sort(a.begin(), a.end(), greater());
    for(int i = 0; i < n; i++) {
        l[a[i].idx] = segtree.qryMx(0, max(a[i].idx, 0));
        r[a[i].idx] = segtree.qryMn(min(a[i].idx, n-1), n-1);
        segtree.upd(a[i].idx);
        int x = a[i].idx;
        int y = l[a[i].idx];
        int z = r[a[i].idx];
        if(y>=0) connect(x, y);
        if(z<=n-1) connect(x, z);
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    vector<int> dist(n, -1);
    queue<int> bfs;
    for(int i = a; i <= b; i++) {
        dist[i] = 0;
        bfs.push(i);
    }
    while(!bfs.empty()) {
        int curr = bfs.front(); bfs.pop();
        if(c <= curr && curr <= d) return dist[curr];

        for(auto i : adjList[curr]) {
            if(dist[i] != -1) continue;
            dist[i] = dist[curr] + 1;
            bfs.push(i);
        }
    }
    return -1;
}

• 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