Submission #696132

#	Time	Username	Problem	Language	Result	Execution time	Memory
696132		sharaelong	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	2138 ms	53560 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct SegmentTree {
    int n, h;
    vector<pii> arr;
    SegmentTree(int _n) : n(_n) {
        h = Log2(n);
        n = 1 << h;
        arr.resize(2*n);
        for (int i=n; i<2*n; ++i) arr[i] = { 0, i-n };
        for (int i=n-1; i>=0; --i) arr[i] = { 0, arr[2*i].second };
    }

    void update(int pos, int c) {
        pos += n;
        arr[pos] = { c, pos-n };
        for (pos /= 2; pos > 0; pos /= 2) {
            arr[pos] = (arr[2*pos].first > arr[2*pos+1].first ? arr[2*pos] : arr[2*pos+1]);
        }
    }

    pii query(int l, int r) {
        l += n, r += n;
        pii ret = {0,-1};
        for (; l <= r; l/=2, r/=2) {
            if (l & 1) ret = (ret.first > arr[l].first ? ret : arr[l]), l++;
            if (~r & 1) ret = (ret.first > arr[r].first ? ret : arr[r]), r--;
        }
        return ret;
    }

    static int Log2(int x){
        int ret = 0;
        while (x > (1 << ret)) ret++;
        return ret;
    }
};

const int MAX_N = 2e5 + 1;

int n;
int h[MAX_N];
vector<int> adj[MAX_N];
int depth[MAX_N];
int large_sparse[18][MAX_N];
int sparse[18][MAX_N];
SegmentTree seg(MAX_N);

void dfs(int here) {
    for (int there: adj[here]) {
        depth[there] = depth[here] + 1;
        dfs(there);
    }
}

void init(int N, vector<int> H) {
    n = N;
    for (int i=0; i<n; ++i) h[i] = H[i];
    for (int i=0; i<n; ++i) seg.update(i, h[i]);
    
    vector<pii> nxt(n, {-1,-1});
    for (int i=0; i<n; ++i) {
        int l = i+1, r = n-1;
        while (l < r) {
            int m = (l+r)/2;
            if (seg.query(i+1, m).first > h[i]) {
                r = m;
            } else {
                l = m+1;
            }
        }
        if (l < n-1 || h[l] >= h[i]) nxt[i].second = l;
    }
    for (int i=0; i<n; ++i) {
        int l = 0, r = i-1;
        while (l < r) {
            int m = (l+r+1)/2;
            if (seg.query(m, i-1).first > h[i]) {
                l = m;
            } else {
                r = m-1;
            }
        }
        if (r > 0 || h[r] >= h[i]) nxt[i].first = r;
    }

    memset(sparse, -1, sizeof sparse);
    memset(large_sparse, -1, sizeof large_sparse);
    for (int i=0; i<n; ++i) {
        // cout << i << ' ' << nxt[i].first << ' ' << nxt[i].second << endl;
        if (nxt[i].first != -1 && nxt[i].second != -1) {
            large_sparse[0][i] = (h[nxt[i].first] > h[nxt[i].second] ? nxt[i].first : nxt[i].second);
            sparse[0][i] = (h[nxt[i].first] > h[nxt[i].second] ? nxt[i].second : nxt[i].first);
        } else {
            large_sparse[0][i] = (nxt[i].first == -1 ? nxt[i].second : nxt[i].first);
            sparse[0][i] = large_sparse[0][i];
        }
        if (sparse[0][i] != -1) adj[sparse[0][i]].push_back(i);
        // cout << i << ' ' << sparse[0][i] << ' ' << large_sparse[0][i] << endl;
    }
    for (int i=1; i<18; ++i) {
        for (int j=0; j<n; ++j) {
            if (sparse[i-1][j] != -1) sparse[i][j] = sparse[i-1][sparse[i-1][j]];
            if (large_sparse[i-1][j] != -1) large_sparse[i][j] = large_sparse[i-1][large_sparse[i-1][j]];
        }
    }
    dfs(seg.query(0, n-1).second);
}

bool is_reachable(int here, int par) {
    int d = max(0, depth[here] - depth[par]);
    for (int i=17; i>=0; --i) {
        if (d & (1 << i)) {
            here = sparse[i][here];
        }
    }
    return here == par;
}

int onetoone(int from, int to) {
    if (!is_reachable(from, to)) return -1;
    int ret = 0;
    for (int i=17; i>=0; --i) {
        if (large_sparse[i][from] != -1 && is_reachable(large_sparse[i][from], to)) {
            from = large_sparse[i][from];
            ret += (1 << i);
        }
    }
    return ret + depth[from] - depth[to];
}

int lowa(int x, int y, int m) {
    int l = x, r = y;
    while (l < r) {
        int mid = (l+r+1)/2;
        if (seg.query(mid, y).first > m) {
            l = mid;
        } else {
            r = mid-1;
        }
    }
    if (l > x || h[l] > m) return l;
    else return -1;
}

int minimum_jumps(int A, int B, int C, int D) {
    auto[m, midx] = seg.query(B+1, C-1);
    if (seg.query(C, D).first < m) return -1;
    int la = lowa(0, B, m);
    if (la < A) {
        auto[highest, idx] = seg.query(A, B);
        if (la == -1) return onetoone(idx, midx) + 1;
        int ret = onetoone(idx, midx) + 1;
        if (seg.query(C, D).first > h[la]) ret = min(ret, onetoone(idx, la) + 1);
        return ret;
    } else {
        if (seg.query(C, D).first > h[la]) return 1;
        int from = seg.query(la+1, B).second;
        if (from == -1) return -1;
        return onetoone(from, midx) + 1;
    }
}

• 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