Submission #1282110

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

jumps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if(!(cin >> n >> q)) return 0;
    vector<int> h(n);
    for(int i = 0; i < n; ++i) cin >> h[i];

    // build graph: from i -> nearest greater on left (if exists), and i -> nearest greater on right (if exists)
    vector<vector<int>> g(n);

    // nearest greater to the left
    {
        stack<int> st;
        for(int i = 0; i < n; ++i){
            while(!st.empty() && h[st.top()] <= h[i]) st.pop();
            if(!st.empty()){
                g[i].push_back(st.top());
            }
            st.push(i);
        }
    }

    // nearest greater to the right
    {
        stack<int> st; // new empty stack
        for(int i = n-1; i >= 0; --i){
            while(!st.empty() && h[st.top()] <= h[i]) st.pop();
            if(!st.empty()){
                g[i].push_back(st.top());
            }
            st.push(i);
        }
    }

    // process queries
    while(q--){
        int A,B,C,D;
        cin >> A >> B >> C >> D; // input uses 0-based indices in the problem statement example
        // multi-source BFS from all s in [A,B]
        vector<int> dist(n, INF);
        queue<int> Q;
        for(int s = A; s <= B; ++s){
            if(dist[s] > 0){
                dist[s] = 0;
                Q.push(s);
            }
        }
        while(!Q.empty()){
            int u = Q.front(); Q.pop();
            for(int v : g[u]){
                if(dist[v] > dist[u] + 1){
                    dist[v] = dist[u] + 1;
                    Q.push(v);
                }
            }
        }
        int ans = INF;
        for(int e = C; e <= D; ++e) ans = min(ans, dist[e]);
        if(ans == INF) cout << -1 << '\n';
        else cout << ans << '\n';
    }

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccDBnViG.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccrNT5YL.o:jumps.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccDBnViG.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