Submission #1118714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118714		Zero_OP	Rainforest Jumps (APIO21_jumps)	C++14	Compilation error	0 ms	0 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e3 + 5;
const int inf = 1e9;

int N, H[MAX];
vector<int> adj[MAX];
int rmq[11][11][MAX][MAX];

vector<int> bfs(int s){
    vector<int> d(N, inf);
    queue<int> q;
    q.push(s);
    d[s] = 0;

    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto v : adj[u]){
            if(d[v] == inf){
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }

    return d;
}

void init(int _N, int _H[]){
    N = _N;
    copy(_H, _H + N, H);

    stack<int> st;
    for(int i = 0; i < N; ++i){
        while(!st.empty() && H[st.top()] <= H[i]) st.pop();
        if(!st.empty()) adj[i].emplace_back(st.top());
        st.push(i);
    }

    stack<int>().swap(st);
    for(int i = N - 1; i >= 0; --i){
        while(!st.empty() && H[st.top()] <= H[i]) st.pop();
        if(!st.empty()) adj[i].emplace_back(st.top());
        st.push(i);
    }

    for(int i = 0; i < N; ++i){
        vector<int> d = bfs(i);
        for(int j = 0; j < N; ++j){
            rmq[0][0][i][j] = d[j];
        }
    }

    for(int u = 0; (1 << u) <= N; ++u){
        for(int i = 0; i + (1 << u) <= N; ++i){
            for(int v = 0; (1 << v) <= N; ++v){
                for(int j = 0; j + (1 << v) <= N; ++j){
                    if(u == 0){
                        if(v > 0){
                            rmq[u][v][i][j] = min(rmq[u][v - 1][i][j], rmq[u][v - 1][i][j  + (1 << (v - 1))]);
                        }
                    } else{
                        rmq[u][v][i][j] = min(rmq[u - 1][v][i][j], rmq[u - 1][v][i + (1 << (u - 1))][j]);
                    }
                }
            }
        }
    }
}

int minimum_jumps(int a, int b, int c, int d){
    int u = 31 - __builtin_clz(b - a + 1);
    int v = 31 - __builtin_clz(d - c + 1);

    int cur = min({rmq[u][v][a][c], rmq[u][v][a][d - (1 << v) + 1],
                   rmq[u][v][b - (1 << u) + 1][c], rmq[u][v][b - (1 << u) + 1][d - (1 << v) + 1]});
    return (cur == inf ? -1 : cur);
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    int N, Q;
    cin >> N >> Q;

    int H[N];
    for(int i = 0; i < N; ++i){
        cin >> H[i];
    }

    init(N, H);

    for(int i = 0; i < Q; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d) << '\n';
    }

    return 0;
}
#endif //LOCAL

Compilation message (stderr)

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