Submission #1275333

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

jumps

#include <bits/stdc++.h>
#include "jumps.h"

using namespace std;

int n, q, lpos, rpos, des, mid, sta, res;
int h[200000], l[200000], r[200000];
int high[20][200000], low[20][200000], sp[20][200000];
vector<int> v;

inline int Get_sp(int _l, int _r)
{
    int _k = __lg(_r - _l + 1);
    _l = sp[_k][_l];
    _r = sp[_k][_r - (1 << _k) + 1];
    return (h[_l] > h[_r] ? _l : _r);
}

inline int Go(int start_pos, int end_pos)
{
    int ret = 0;
    for (int i = 19, j; i >= 0; --i)
    {
        j = high[i][start_pos];
        if (j != -1 && h[j] < h[end_pos])
        {
            start_pos = j;
            ret += (1 << i);
        }
    }
    for (int i = 19, j; i >= 0; --i)
    {
        j = low[i][start_pos];
        if (j != -1 && h[j] < h[end_pos])
        {
            start_pos = j;
            ret += (1 << i);
        }
    }
    return ret + 1;
}

void init(int N, int(H[]))
{
    n = N;
    for (int i = 0; i < n; ++i)
    {
        h[i] = H[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> h[i];
        while (!v.empty() && h[v.back()] <= h[i])
        {
            v.pop_back();
        }
        l[i] = (v.empty() ? -1 : v.back());
        v.push_back(i);
    }
    v.clear();
    for (int i = n - 1; i >= 0; --i)
    {
        while (!v.empty() && h[v.back()] <= h[i])
        {
            v.pop_back();
        }
        r[i] = (v.empty() ? -1 : v.back());
        v.push_back(i);
        high[0][i] = (l[i] == -1 ? r[i] : (r[i] == -1 ? l[i] : (h[l[i]] > h[r[i]] ? l[i] : r[i])));
        low[0][i] = (l[i] == -1 ? r[i] : (r[i] == -1 ? l[i] : (h[l[i]] < h[r[i]] ? l[i] : r[i])));
        sp[0][i] = i;
    }
    for (int i = 1; i < 20; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            lpos = high[i - 1][j];
            high[i][j] = (lpos == -1 ? -1 : high[i - 1][lpos]);
            lpos = low[i - 1][j];
            low[i][j] = (lpos == -1 ? -1 : low[i - 1][lpos]);
        }
        for (int j = 0; j + (1 << i) <= n; ++j)
        {
            lpos = sp[i - 1][j];
            rpos = sp[i - 1][j + (1 << (i - 1))];
            sp[i][j] = (h[lpos] > h[rpos] ? lpos : rpos);
        }
    }
}

int minimum_jumps(int a, int b, int c, int d)
{
    des = Get_sp(c, d);
    mid = (b + 1 < c ? Get_sp(b + 1, c - 1) : -1);
    sta = -1;
    for (int i = 19, j = b + 1; i >= 0; --i)
    {
        if (a <= j - (1 << i) && h[Get_sp(j - (1 << i), b)] < h[des])
        {
            j -= (1 << i);
            sta = Get_sp(j, b);
        }
    }
    if (sta == -1 || (mid != -1 && h[mid] >= h[des]))
    {
        return -1;
    }
    if (mid == -1)
    {
        return (h[b] <= h[des] ? 1 : -1);
    }
    if (h[sta] >= h[mid])
    {
        res = Go(sta, des);
    }
    else
    {
        res = Go(sta, mid) + 1;
        if (l[mid] != -1 && h[l[mid]] < h[des])
        {
            res = min(res, Go(sta, l[mid]) + 1);
        }
    }
    return res;
}

// int main()
// {
//     return 0;
// }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccSRa4Tp.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