Submission #1191917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191917		duyngadocton	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	532 ms	73388 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ii pair<int,int>
#define ll long long
#define pb push_back
#define eb emplace_back

const int MAX = (int) 2e5;
const int inf = (int) 1e9;

int n, h[MAX + 5];
ii mx[25][MAX + 5];
int lg[MAX + 5];
int fmx[25][MAX + 5];
int posmax[25][MAX + 5];
int fnxt[25][MAX + 5];
int pre[MAX + 5], nxt[MAX + 5];

int getmax(int l, int r) {
    int k = lg[r - l + 1];
    return max(mx[k][l], mx[k][r - (1 << k) + 1]).se;
}

void build() {
    pre[0] = 0, nxt[n + 1] = n + 1;
    h[0] = h[n + 1] = inf;
    for(int i = 1; i <= n; ++i) {
        int j = i - 1;
        while(j > 0 && h[j] <= h[i]) j = pre[j];
        pre[i] = j;
    }
    for(int i = n; i >= 1; --i) {
        int j = i + 1;
        while(j <= n && h[j] <= h[i]) j = nxt[j];
        nxt[i] = j;
    }
    for(int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
    for(int i = 1; i <= n; ++i) mx[0][i] = ii(h[i], i);
    for(int k = 1; k <= lg[n]; ++k)
        for(int i = 1; i + (1 << k) - 1 <= n; ++i) mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
    for(int i = 1; i <= n; ++i) {
        int ptr = 0;
        if(pre[i] == 0 && nxt[i] == n + 1) ptr = 0;
        else if(pre[i] == 0) ptr = nxt[i];
        else if(nxt[i] == n + 1) ptr = pre[i];
        else ptr = (h[pre[i]] > h[nxt[i]]) ? pre[i] : nxt[i];
        fmx[0][i] = ptr;
        posmax[0][i] = ptr;
    }
    for(int k = 1; k <= lg[n]; ++k)
        for(int i = 1; i <= n; ++i) fmx[k][i] = fmx[k - 1][fmx[k - 1][i]], posmax[k][i] = max(posmax[k - 1][i], posmax[k - 1][fmx[k - 1][i]]);
    for(int i = 1; i <= n; ++i) fnxt[0][i] = nxt[i];
    for(int k = 1; k <= lg[n]; ++k)
        for(int i = 1; i <= n; ++i) fnxt[k][i] = fnxt[k - 1][fnxt[k - 1][i]];
}

void init(int N, vector<int> H) {
    n = N;
    for(int i = 1; i <= n; ++i) h[i] = H[i - 1];
    build();
}

int solve(int A, int B, int C, int D) {
    int pos = getmax(C, D);
    int lo = A - 1, hi = B;
    while(hi - lo > 1) {
        int mid = lo + hi >> 1;
        if(h[getmax(mid, B)] > h[pos]) lo = mid;
        else hi = mid;
    }
    int start = getmax(hi, B);
    int cur = start;
    int dem = 0;
    cur = start;
    for(int k = lg[n]; k >= 0; --k) {
        if(posmax[k][cur] < C && h[fmx[k][cur]] < h[pos]) cur = fmx[k][cur], dem += (1 << k);
    }
    if(h[fmx[0][cur]] > h[pos]) {
        for(int k = lg[n]; k >= 0; --k) if(h[fnxt[k][cur]] <= h[pos] && cur < C) cur = fnxt[k][cur], dem += (1 << k);
        return dem;
    }
    else {
        return dem + 1 ;
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    ++A, ++B, ++C, ++D;
    if(h[getmax(B, C - 1)] > h[getmax(C, D)]) return -1;
    if(C == D && C - 1 == B) {
        return solve(A, B, C, C);
    }
    int X = solve(A, B, C, C);
    ++C;
    int pos = getmax(B + 1, C - 1);
    X = min(X, solve(A, B, pos, pos) + 1);
    pos = getmax(C, D);
    int lo = A - 1, hi = B;
    while(hi - lo > 1) {
        int mid = lo + hi >> 1;
        if(h[getmax(mid, B)] > h[pos]) lo = mid;
        else hi = mid;
    }
    if(h[getmax(hi, pos)] > h[pos]) return -1;
    int start = getmax(hi, B);
    int cur = start;
    int MX = getmax(B + 1, C - 1);
    int dem  = 0;
    for(int k = lg[n]; k >= 0; --k) if(h[fmx[k][cur]] < h[MX]) {
        cur = fmx[k][cur];
        dem += (1 << k);
    }
    if(h[fmx[0][cur]] >= h[MX]) ++dem, cur = fmx[0][cur];
    ++dem;
    return min(dem, X);
}

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