Submission #1275242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275242		cnam9	Rainforest Jumps (APIO21_jumps)	C++20	Compilation error	0 ms	0 KiB

jumps

#include <bits/stdc++.h>

// #include <stack>
// #include <queue>

// #include <limits>
// #include <climits>

// #include <math.h>


using namespace std;

constexpr int N = 2e5 + 5;
constexpr int logN = static_cast<int>(log2(N));

template <typename T>
inline T mymin(T x, T y) {
    return x < y ? x : y;
}
template <typename T>
inline T mymax(T x, T y) {
    return x > y ? x : y;
}
#define min mymin
#define max mymax

int n, q;
int *h;

int Next[N], Prev[N];

int highUp[logN + 1][N];
int lowUp[logN + 1][N];
int prevUp[logN + 1][N];
int nextUp[logN + 1][N];

int minTable[logN + 1][N];
pair<int, int> maxTable[logN + 1][N];

template <auto f, auto st>
void buildSparseTable() {
    for (int k = 1; k <= logN; k++) {
        for (int i = 0; i + (1 << k) <= n; i++)
            st[k][i] = f(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
    }
}

template <auto up>
void buildUpTable() {
    for (int k = 0; k < logN; k++) {
        for (int i = 0; i <= n; i++)
            up[k + 1][i] = up[k][up[k][i]];
    }
}

template <auto f, auto st>
auto query(int l, int r) {
    int k = 31 - __builtin_clz(r - l);
    return f(st[k][l], st[k][r - (1 << k)]);
}

int query(int a, int b, int c) {

    int res = 0;

    for (int k = logN; k >= 0; k--) {
        if (prevUp[k][b] < a || h[prevUp[k][b]] > h[c]) continue;
        b = prevUp[k][b];
    }

    for (int k = logN; k >= 0; k--) {
        if (h[highUp[k][b]] > h[c]) continue;
        b = highUp[k][b];
        res += 1 << k;
    }
    for (int k = logN; k >= 0; k--) {
        if (h[lowUp[k][b]] > h[c]) continue;
        b = lowUp[k][b];
        res += 1 << k;
    }

    if (b != c) {
        return -1;
    }

    return res;
}

int rquery(int a, int b, int c) {

    int res = 0;

    for (int k = logN; k >= 0; k--) {
        if (nextUp[k][a] > b || h[nextUp[k][a]] > h[c]) continue;
        a = nextUp[k][a];
    }

    for (int k = logN; k >= 0; k--) {
        if (h[highUp[k][a]] > h[c]) continue;
        a = highUp[k][a];
        res += 1 << k;
    }
    for (int k = logN; k >= 0; k--) {
        if (h[lowUp[k][a]] > h[c]) continue;
        a = lowUp[k][a];
        res += 1 << k;
    }

    if (a != c) {
        return -1;
    }

    return res;
}

void init(int N, int *H) {
    n = N;
    h = H;

    h[n] = N;

    stack<int> stk;
    stk.push(n);
    for (int i = 0; i < n; i++) {
        while (h[stk.top()] <= h[i]) {
            stk.pop();
        }
        Prev[i] = stk.top();
        stk.push(i);
    }
    
    while (!stk.empty()) stk.pop();
    stk.push(n);
    for (int i = n - 1; i >= 0; i--) {
        while (h[stk.top()] <= h[i]) {
            stk.pop();
        }
        Next[i] = stk.top();
        stk.push(i);
    }

    for (int i = 0; i < n; i++) {
        highUp[0][i] = h[Next[i]] < h[Prev[i]] ? Prev[i] : Next[i];
        lowUp[0][i]  = h[Next[i]] < h[Prev[i]] ? Next[i] : Prev[i];
        prevUp[0][i] = Prev[i];
        nextUp[0][i] = Next[i];
    }
    highUp[0][n] = n;
    lowUp[0][n] = n;
    prevUp[0][n] = n;
    nextUp[0][n] = n;

    buildUpTable<highUp>();
    buildUpTable<lowUp>();
    buildUpTable<prevUp>();
    buildUpTable<nextUp>();

    for (int i = 0; i < n; i++) {
        minTable[0][i] = h[i];
        maxTable[0][i] = {h[i], i};
    }
    buildSparseTable<min<int>, minTable>();
    buildSparseTable<max<pair<int, int>>, maxTable>();
}

int query(int a, int b, int c, int d) {

    if (c == d) {
        return query(a, b, c);
    }

    int minsource = query<min<int>, minTable>(a, b + 1);
    int maxdest = query<max<pair<int, int>>, maxTable>(c, d + 1).first;

    if (h[b] > maxdest) {
        for (int k = logN; k >= 0; k--) {
            if (b - (1 << k) < a || minTable[k][b - (1 << k) + 1] <= maxdest) continue;
            b -= 1 << k;
        }
    }

    if (minsource > maxdest || h[b] > maxdest) {
        return -1;
    }

    if (b + 1 == c) {
        return 1;
    }

    int newa = b + 1;
    for (int k = logN; k >= 0; k--) {
        if (newa - (1 << k) < a || maxTable[k][newa - (1 << k)].first >= maxdest) continue;
        newa -= 1 << k;
    }
    a = newa;

    int maxsource = query<max<pair<int, int>>, maxTable>(a, b + 1).first;
    int x = query<max<pair<int, int>>, maxTable>(b + 1, c).second;
    
    if (h[x] > maxdest) {
        return -1;
    }

    if (maxsource > h[x]) {
        return 1;
    }

    int ans = query(a, b, x);
    if (Prev[x] < a && h[Prev[x]] < maxdest) {
        ans = min<unsigned int>(ans, rquery(a, b, Prev[x]));
    }

    return ans == -1 ? -1 : ans + 1;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccU8lDjw.o: in function `main':
stub.cpp:(.text.startup+0x159): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: stub.cpp:(.text.startup+0x1c1): undefined reference to `minimum_jumps(int, int, int, int)'
collect2: error: ld returned 1 exit status