제출 #1275244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275244		cnam9	밀림 점프 (APIO21_jumps)	C++20	컴파일 에러	0 ms	0 KiB

jumps

#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));

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 build() {
    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 build() {
    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] = numeric_limits<int>::max();

    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;

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

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

int minimum_jumps(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;
}

컴파일 시 표준 에러 (stderr) 메시지

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