Submission #1318045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318045		aris12345678	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4082 ms	14492 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> height, dist;
vector<vector<int>> adj;

void init(int N, vector<int> H) {
    n = N;
    height = H;
    adj.resize(N);
    stack<int> left, right;
    for(int i = 0; i < N; i++) {
        while(!left.empty() && H[left.top()] < H[i])
            left.pop();
        if(!left.empty())
            adj[i].push_back(left.top());
        left.push(i);
    }
    for(int i = N-1; i >= 0; i--) {
        while(!right.empty() && H[right.top()] < H[i])
            right.pop();
        if(!right.empty())
            adj[i].push_back(right.top());
        right.push(i);
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    queue<int> q;
    dist.assign(n, INT_MAX);
    for(int i = A; i <= B; i++) {
        q.push(i);
        dist[i] = 0;
    }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        if(u >= C && u <= D) continue;
        for(int i = 0; i < adj[u].size(); i++) {
            if(dist[adj[u][i]] > dist[u]+1) {
                q.push(adj[u][i]);
                dist[adj[u][i]] = dist[u]+1;
            }
        }
    }
    int ans = INT_MAX;
    for(int i = C; i <= D; i++)
        ans = min(ans, dist[i]);
    if(ans == INT_MAX) return -1;
    return ans;
}

// int main() {
//     int N, Q;
//     scanf("%d %d", &N, &Q);
//     vector<int> H(N);
//     for(int i = 0; i < N; i++)
//         scanf("%d", &H[i]);
//     init(N, H);
//     while(Q--) {
//         int A, B, C, D;
//         scanf("%d %d %d %d", &A, &B, &C, &D);
//         printf("%d\n", minimum_jumps(A, B, C, D));
//     }
//     return 0;
// }

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19