Submission #980494

#	Time	Username	Problem	Language	Result	Execution time	Memory
980494		vjudge1	밀림 점프 (APIO21_jumps)	C++17	0 / 100	149 ms	96700 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

int n;
int A[N];
int B[N];
int a[N];
int t[N][20];
int t2[N][20];
int L[N];
int f[N][20];

int comb_t(int i, int j) {
    return a[i] > a[j] ? i : j;
}

int comb_f(int i, int j) {
    return B[i] > B[j] ? i : j;
}

int get_f(int l, int r) {
    int g = L[r - l + 1];
    return comb_f(f[l][g], f[r - (1 << g) + 1][g]);
}

void init(int N_, std::vector<int> H) {
    for (int i = 2; i < N; i++) {
        L[i] = L[i / 2] + 1;
    }
    n = N_;

    vector<int> v;
    for (int i = 0; i < n; i++) {
        a[i] = H[i];

        while (!v.empty() && H[i] > H[v.back()]) {
            v.pop_back();
        }
        if (v.empty()) {
            A[i] = -1;
        } else {
            A[i] = v.back();
        }
        v.push_back(i);
    }
    v.clear();
    B[n] = n;
    for (int i = n - 1; i >= 0; i--) {
        while (!v.empty() && H[i] > H[v.back()]) {
            v.pop_back();
        }
        if (v.empty()) {
            B[i] = n;
        } else {
            B[i] = v.back();
        }
        v.push_back(i);
    }

    t[n][0] = n;
    t2[n][0] = n;
    for (int i = 0; i < n; i++) {
        if (A[i] == -1 || B[i] == n) {
            t[i][0] = n;
        } else {
            t[i][0] = comb_t(A[i], B[i]);
        }
        f[i][0] = i;
        t2[i][0] = B[i];
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j <= n; j++) {
            t[j][i] = t[t[j][i - 1]][i - 1];
            t2[j][i] = t2[t2[j][i - 1]][i - 1];

            if (j + (1 << i) - 1 < n) {
                f[j][i] = comb_f(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
            }
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int l = A, r = B + 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (::B[get_f(m, B)] <= D) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    if (l == B + 1) {
        return -1;
    } else if (::B[get_f(l, B)] >= C) {
        return 1;
    }

    int x = get_f(l, B);

    assert (x == B);

    int res = 0;
    for (int i = 19; i >= 0; i--) {
        if (::B[t[x][i]] < C) {
            x = t[x][i];
            res += (1 << i);
        }
    }

    x = t[x][0];
    res += 1;

    for (int i = 19; i >= 0; i--) {
        if (t2[x][i] < C) {
            x = t2[x][i];
            res += (1 << i);
        }
    }

    x = t2[x][0];
    res += 1;

    assert (x >= C);
    if (x > D) {
        return -1;
    }

    return res;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:82:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   82 |                 f[j][i] = comb_f(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
      |                                                           ~~^~~

• Subtask 1: 0 / 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