Submission #737398

#	Time	Username	Problem	Language	Result	Execution time	Memory
737398		phoebe	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	2289 ms	114056 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
#define ALL(x) x.begin(), x.end()

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];
vector<pii> mst[maxn * 4];

void build(int tl = 0, int tr = maxn, int i = 1){
    if (tl == tr){
        tree[i] = tl; 
        mst[i].PB({h[tl], 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]);
    merge(ALL(mst[i * 2]), ALL(mst[i * 2 + 1]), back_inserter(mst[i]));
}

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 get_ub(int l, int r, int x, int tl = 0, int tr = maxn, int i = 1){
    if (l > tr || tl > r) return -1;
    if (l <= tl && tr <= r){
        int idx = lower_bound(ALL(mst[i]), make_pair(x, -1)) - mst[i].begin();
        if (idx == mst[i].size()) return -1;
        return mst[i][idx].S;
    }
    int tm = (tl + tr) / 2;
    int left = get_ub(l, r, x, tl, tm, i * 2), 
    right = get_ub(l, r, x, tm + 1, tr, i * 2 + 1);
    if (h[right] != -1) return right;
    return left;
}

int get_lb(int l, int r, int x, int tl = 0, int tr = maxn, int i = 1){
    if (l > tr || tl > r) return maxn - 1;
    if (l <= tl && tr <= r){
        int idx = upper_bound(ALL(mst[i]), make_pair(x, -1)) - mst[i].begin() - 1;
        if (idx == -1) return maxn - 1;
        return mst[i][idx].S;
    }
    int tm = (tl + tr) / 2;
    int left = get_lb(l, r, x, tl, tm, i * 2), 
    right = get_lb(l, r, x, tm + 1, tr, i * 2 + 1);
    if (h[left] > h[right]) return left;
    return right;
}

int go_right(int s, int c, int d){
    int re = 0;
    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;
}

int find(int a, int b, int v){
    int l = a, r = b, ans = b + 1;
    while (l <= r){
        int mid = (l + r) / 2;
        int mx = h[query(mid, b)];
        if (mx < v) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

int solve(int a, int b, int c, int d){
    int e = query(c, d), mid = query(b, c);
    int rightmost_bad = find(a, b, h[e]);
    int s = get_lb(rightmost_bad, b, h[e]);
    if (s >= n) return INF;
    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];
    }
    return re + min(go_right(s, c, d), 
    go_right(jump_mx[s][0], c, d) + 1);
}

void init(int N, vector<int> H){
    fill(h, h + maxn, INF); h[maxn - 1] = -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 = solve(a, b, c, d);
    return (re < INF ? re : -1);
}

Compilation message (stderr)

jumps.cpp: In function 'int get_ub(int, int, int, int, int, int)':
jumps.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (idx == mst[i].size()) return -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