Submission #954086

#	Time	Username	Problem	Language	Result	Execution time	Memory
954086		Unforgettablepl	Rainforest Jumps (APIO21_jumps)	C++17	21 / 100	4011 ms	62804 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> adj[2000001];
int arr[2000001];
int rarr[2000001];
int n;

void init(int32_t N, vector<int32_t> H) {
    n=N;
    for(int i=0;i<N;i++)arr[i]=H[i];
    for(int i=0;i<N;i++)rarr[arr[i]]=i;
    stack<int> q;
    for(int i=0;i<N;i++){
        while(!q.empty() and q.top()<arr[i])q.pop();
        if(!q.empty())adj[arr[i]].emplace_back(q.top());
        q.emplace(arr[i]);
    }
    while(!q.empty())q.pop();
    for(int i=N-1;i>=0;i--){
        while(!q.empty() and q.top()<arr[i])q.pop();
        if(!q.empty())adj[arr[i]].emplace_back(q.top());
        q.emplace(arr[i]);
    }
}

int32_t minimum_jumps(int32_t A, int32_t B, int32_t C, int32_t D) {
    queue<pair<int,int>> q;
    for(int i=A;i<=B;i++)q.emplace(arr[i],0);
    vector<bool> visited(n);
    while(!q.empty()){
        auto curr = q.front();q.pop();
        if(visited[curr.first])continue;
        visited[curr.first]=true;
        if(C<=rarr[curr.first] and rarr[curr.first]<=D)return curr.second;
        for(int&i:adj[curr.first])if(!visited[i])q.emplace(i,curr.second+1);
    }
    return -1;
}

//int32_t main() {
//    int32_t N, Q;
//    assert(2 == scanf("%d %d", &N, &Q));
//    std::vector<int32_t> H(N);
//    for (int32_t i = 0; i < N; ++i) {
//        assert(1 == scanf("%d", &H[i]));
//    }
//    init(N, H);
//
//    for (int32_t i = 0; i < Q; ++i) {
//        int32_t A, B, C, D;
//        assert(4 == 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: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19