Submission #737362

#	Time	Username	Problem	Language	Result	Execution time	Memory
737362		phoebe	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	4078 ms	52584 KiB

jumps

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

#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
#define PB push_back

const int maxn = 2e5 + 10, INF = 1e9 + 7;
int n, h[maxn], tree[maxn * 4], 
jump_mn[maxn][20], jump_mx[maxn][20], jump_right[maxn][20];

void build(int tl = 0, int tr = maxn, int i = 1){
    if (tl == tr){
        tree[i] = tl; return;
    }
    int tm = (tl + tr) / 2;
    build(tl, tm, i * 2); build(tm + 1, tr, i * 2 + 1);
    tree[i] = (h[tree[i * 2]] > h[tree[i * 2 + 1]] ? 
    tree[i * 2] : tree[i * 2 + 1]);
}

int query(int l, int r, int tl = 0, int tr = maxn, int i = 1){
    if (l > tr || tl > r) return maxn - 1;
    if (l <= tl && tr <= r) return tree[i];
    int tm = (tl + tr) / 2;
    int left = query(l, r, tl, tm, i * 2), 
    right = query(l, r, tm + 1, tr, i * 2 + 1);
    if (h[left] > h[right]) return left;
    return right;
}

int solve(int s, int c, int d){
    int e = query(c, d), mid = query(s, c);
    int re = 0;
    for (int p = 19; p >= 0; p--){
        if (h[jump_mx[s][p]] < h[mid]) re += (1<<p), s = jump_mx[s][p];
    }
    if (h[jump_mx[s][0]] <= h[e]) re++, s = jump_mx[s][0];
    else if (h[jump_mn[s][0]] <= h[e]) re++, s = jump_mn[s][0];
    if (c <= s && s <= d) return re;
    for (int p = 19; p >= 0; p--){
        if (jump_right[s][p] < c) re += (1<<p), s = jump_right[s][p];
    }
    if (c <= jump_right[s][0] && jump_right[s][0] <= d) return re + 1;
    return INF;
}

void init(int N, vector<int> H){
    fill(h, h + maxn, -1);
    n = N;
    FOR(i, n) h[i] = H[i];
    build();
    stack<int> s;
    for (int i = n - 1; i >= 0; i--){
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        int x = (s.empty() ? i : s.top());
        jump_mx[i][0] = jump_mn[i][0] = x;
        jump_right[i][0] = x;
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = 0; i < n; i++){
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        int x = (s.empty() ? i : s.top());
        if (h[x] > h[jump_mx[i][0]] && x != i) jump_mx[i][0] = x;
        if (h[x] < h[jump_mn[i][0]] && x != i) jump_mn[i][0] = x;
        s.push(i);
    }
    for (int p = 1; p < 20; p++){
        FOR(i, n){
            jump_mx[i][p] = jump_mx[jump_mx[i][p - 1]][p - 1];
            jump_mn[i][p] = jump_mn[jump_mn[i][p - 1]][p - 1];
            jump_right[i][p] = jump_right[jump_right[i][p - 1]][p - 1];
        }
    }
}

int minimum_jumps(int a, int b, int c, int d){
    int re = INF;
    for (int i = a; i <= b; i++){
        re = min(re, solve(i, c, d));
    }
    return (re != INF ? re : -1);
}

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