Submission #414614

#	Time	Username	Problem	Language	Result	Execution time	Memory
414614		tatyam	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1654 ms	46288 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
 
int N, lgN;
vector<vector<int>> rmq, low, high;

void init(int N, vector<int> H) {
    ::N = N;
    lgN = __lg(N);
    rmq.assign(lgN + 1, vector<int>(N));
    low.assign(lgN + 1, vector<int>(N, -1));
    high.assign(lgN + 1, vector<int>(N, -1));
    rmq[0] = H;
    for(int i = 0; i < lgN; i++) for(int j = 0; j + (2 << i) <= N; j++) rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
    vector<int> q;
    for(int i = 0; i < N; i++){
        while(q.size() && H[q.back()] < H[i]){
            const int j = q.back();
            q.pop_back();
            low[0][j] = i;
        }
        q.push_back(i);
    }
    for(int i = N; i--; ){
        while(q.size() && H[q.back()] < H[i]){
            const int j = q.back();
            q.pop_back();
            high[0][j] = i;
        }
        q.push_back(i);
    }
    for(int i = 0; i < N; i++) if(int &x = low[0][i], &y = high[0][i]; x != -1 && (y == -1 || H[x] > H[y])) swap(x, y);
    for(int i = 0; i < lgN; i++) for(int j = 0; j < N; j++) if(low[i][j] != -1) low[i + 1][j] = low[i][low[i][j]];
    for(int i = 0; i < lgN; i++) for(int j = 0; j < N; j++) if(high[i][j] != -1) high[i + 1][j] = high[i][high[i][j]];
}

int get(int l, int r){
    const int x = __lg(r - l);
    return max(rmq[x][l], rmq[x][r - (1 << x)]);
}
 
int minimum_jumps(int A, int B, int C, int D) {
    auto& H = rmq[0];
    const int X = get(B, C), Y = get(C, D + 1);
    if(X >= Y) return -1;
    {
        int a = B;
        for(int i = lgN; i >= 0; i--) if(const int a2 = a - (1 << i); a2 >= A && get(a2, B + 1) < Y) a = a2;
        A = a;
    }
    const int s = get(A, B + 1);
    if(s >= X) return 1;
    int ans = 2, at = A;
    for(int i = lgN; i >= 0; i--) if(const int at2 = at + (1 << i); at2 < B + 1 && get(at2, B + 1) >= s) at = at2;
    for(int i = lgN; i >= 0; 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 = lgN; i >= 0; 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