Submission #412480

#	Time	Username	Problem	Language	Result	Execution time	Memory
412480		tatyam	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1563 ms	45088 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
void chmax(int& a, int b){ if(a < b) a = b; }

int N;
vector<int> H, RMQ, idx;
vector<vector<int>> low, high;

int get(int l, int r){
    int ans = 0;
    for(l += N, r += N; l < r; l >>= 1, r >>= 1){
        if(l & 1) chmax(ans, RMQ[l++]);
        if(r & 1) chmax(ans, RMQ[--r]);
    }
    return ans;
}
int get_idx(int l, int r){
    int ans = N;
    for(l += N, r += N; l < r; l >>= 1, r >>= 1){
        if(l & 1){
            if(H[ans] < H[idx[l]]) ans = idx[l];
            l++;
        }
        if(r & 1){
            r--;
            if(H[ans] < H[idx[r]]) ans = idx[r];
        }
    }
    return ans;
}

void init(int N, vector<int> H) {
    ::N = N;
    ::H = H;
    RMQ.resize(N);
    RMQ.insert(RMQ.end(), H.begin(), H.end());
    for(int i = N; --i; ) RMQ[i] = max(RMQ[i << 1], RMQ[i << 1 | 1]);
    idx.resize(N * 2);
    for(int i = 0; i < N; i++) idx[N + i] = i;
    for(int i = N; --i; ) idx[i] = H[idx[i << 1]] > H[idx[i << 1 | 1]] ? idx[i << 1] : idx[i << 1 | 1];
    ::H.push_back(0);
    set<int> idx;
    for(int i = 0; i < N; i++) idx.insert(idx.end(), i);
    vector<int> h(N);
    iota(h.begin(), h.end(), 0);
    sort(h.begin(), h.end(), [&](int x, int y){ return H[x] < H[y]; });
    low.assign(18, vector<int>(N, -1));
    high.assign(18, vector<int>(N, -1));
    for(int i : h){
        auto p = idx.find(i);
        if(p != idx.begin()) high[0][i] = *prev(p);
        p = idx.erase(p);
        if(p != idx.end()){
            if(high[0][i] == -1) high[0][i] = *p;
            else{
                low[0][i] = *p;
                if(H[low[0][i]] > H[high[0][i]]) swap(low[0][i], high[0][i]);
            }
        }
    }
    for(int i = 0; i < 17; i++) for(int j = 0; j < N; j++){
        if(low[i][j] != -1) low[i + 1][j] = low[i][low[i][j]];
        if(high[i][j] != -1) high[i + 1][j] = high[i][high[i][j]];
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    const int X = get(B, C), Y = get(C, D + 1);
    if(X >= Y) return -1;
    if(get(A, B + 1) >= Y){
        int ok = B, ng = A;
        while(ok - ng > 1){
            const int cen = (ok + ng) / 2;
            (get(cen, B + 1) >= Y ? ng : ok) = cen;
        }
        A = ok;
    }
    if(get(A, B + 1) >= X) return 1;
    int ans = 2, at = get_idx(A, B + 1);
    for(int i = 18; i--; ) if(high[i][at] != -1 && H[high[i][at]] < X){
        ans += 1 << i;
        at = high[i][at];
    }
    if(high[0][at] != -1 && H[high[0][at]] < Y) return ans;
    for(int i = 18; i--; ) if(low[i][at] != -1 && H[low[i][at]] < X){
        ans += 1 << i;
        at = low[i][at];
    }
    return ans;
}

• 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