Submission #865016

#	Time	Username	Problem	Language	Result	Execution time	Memory
865016		hgmhc	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	921 ms	78780 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x, y) x = max(x, y)
#define mup(x, y) x = min(x, y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define ensure(...) if (!(__VA_ARGS__)) { fprintf(stderr, "Error in %dth line.", __LINE__), exit(-1); }

template <const int N>
struct segtree {
    int t[2*N]{};
    int &operator [] (int i){ return t[N+i]; }
    void build() {
        per(i,1,N-1) t[i] = max(t[2*i],t[2*i+1]);
    }
    int Max(int a, int b) {
        int res = 0;
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) Mup(res,t[a]);
            if (~b&1) Mup(res,t[b]);
        }
        return res;
    }
};

const int N = 2e5;

vi adj[N];
int max_jmp[N][20], min_jmp[N][20], lft_jmp[N][20], rgt_jmp[N][20], Arg[N+1];
segtree<N> h;

void construct_graph(int n, vi &H) {
    stack<int> S;
    rep(i,0,n-1) {
        while (not S.empty() and H[S.top()] < H[i]) S.pop();
        if (not S.empty()) adj[i].push_back(S.top());
        S.push(i);
    }
    while (not S.empty()) S.pop();
    per(i,0,n-1) {
        while (not S.empty() and H[S.top()] < H[i]) S.pop();
        if (not S.empty()) adj[i].push_back(S.top());
        S.push(i);
    }
}

void construct_sparsetable(int n, vi &H) {
    rep(i,0,n-1) {
        ensure(not adj[i].empty() or H[i] == n);
        if (adj[i].empty()) {
            max_jmp[i][0] = min_jmp[i][0] = lft_jmp[i][0] = rgt_jmp[i][0] = i;
        }
        else if (siz(adj[i]) == 1) {
            max_jmp[i][0] = min_jmp[i][0] = adj[i][0];
            lft_jmp[i][0] = adj[i][0] < i ? adj[i][0] : i;
            rgt_jmp[i][0] = adj[i][0] > i ? adj[i][0] : i;
        }
        else if (siz(adj[i]) == 2) {
            max_jmp[i][0] = adj[i][0], min_jmp[i][0] = adj[i][1];
            if (H[max_jmp[i][0]] < H[min_jmp[i][0]]) swap(max_jmp[i][0],min_jmp[i][0]);
            lft_jmp[i][0] = adj[i][0], rgt_jmp[i][0] = adj[i][1];
            if (lft_jmp[i][0] > rgt_jmp[i][0]) swap(lft_jmp[i][0],rgt_jmp[i][0]);
        }
        else ensure(0);
    }
    rep(k,1,19) rep(i,0,n-1) {
        max_jmp[i][k] = max_jmp[max_jmp[i][k-1]][k-1];
        min_jmp[i][k] = min_jmp[min_jmp[i][k-1]][k-1];
        lft_jmp[i][k] = lft_jmp[lft_jmp[i][k-1]][k-1];
        rgt_jmp[i][k] = rgt_jmp[rgt_jmp[i][k-1]][k-1];
    }
}

void init(int N, vi H) {
    construct_graph(N, H);
    construct_sparsetable(N, H);
    rep(i,0,N-1) h[i] = H[i], Arg[H[i]] = i;
    h.build();
}

int A, B, C, D, hurdle, E;
const int INF = 1e9;

int minimum_jumps(int A, int B, int C, int D) {
    if (h.Max(B,C-1) > h.Max(C,D)) return -1;
    hurdle = h.Max(B+1,C-1);

    if (h[B] >= hurdle) return 1;

    int x = B, ans = INF;
    per(i,0,19) while (A <= lft_jmp[x][i]&&lft_jmp[x][i] < x and h[lft_jmp[x][i]] < hurdle) x = lft_jmp[x][i];

    { // Case. (나)
        int y = lft_jmp[x][0];
        if (A <= y&&y < x) {
            ensure(h[y] >= hurdle);
            y = rgt_jmp[y][0];
            if (C <= y&&y <= D) return 1;
        }
    }

    { // Case. (가)&(다)
        if (C <= rgt_jmp[B][0]&&rgt_jmp[B][0] <= D) return 1;

        int y = x, d = 0;
        per(i,0,19) while (y < C && y != max_jmp[y][i] and h[max_jmp[y][i]] < hurdle) {
            y = max_jmp[y][i], d += 1<<i;
        }
        if (h[max_jmp[y][0]] >= hurdle) {
            int z = max_jmp[y][0];
            if (z < C) {
                if (C <= rgt_jmp[z][0]&&rgt_jmp[z][0] <= D) {
                    return d+1+(z!=y);
                }
            } else {
                if (C <= z&&z <= D) {
                    return d+(z!=y);
                }
            }
        }

        per(i,0,19) while (y < C && y != min_jmp[y][i] and h[min_jmp[y][i]] < hurdle) {
            y = min_jmp[y][i], d += 1<<i;
        }
        if (h[min_jmp[y][0]] >= hurdle) {
            int z = min_jmp[y][0];
            if (z < C) {
                if (C <= rgt_jmp[z][0]&&rgt_jmp[z][0] <= D) {
                    return d+1+(z!=y);
                }
            } else {
                if (C <= z&&z <= D) {
                    return d+(z!=y);
                }
            }
        }
    }
    ensure(0);
}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:98:16: warning: unused variable 'ans' [-Wunused-variable]
   98 |     int x = B, ans = INF;
      |                ^~~

• 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