Submission #690429

#	Time	Username	Problem	Language	Result	Execution time	Memory
690429		Dan4Life	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4027 ms	15212 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back

const int maxn = (int)2e5+10;
const int INF = (int)1e9;

bool increasing;
vector<int> adj[maxn];
int n, dis[maxn], pr[maxn], nx[maxn];

int bfs(int s1, int s2, int d1, int d2){
    queue<int> Q;
    while(!Q.empty()) Q.pop();
    for(int i = 0; i < n; i++) dis[i]=INF;
    for(int i = s1; i <= s2; i++) Q.push(i), dis[i]=0;
    while(!Q.empty()){
        int s = Q.front(); Q.pop();
        if(d1<=s and s<=d2) return dis[s];
        for(auto u : adj[s]){
            if(dis[u]==INF){
                dis[u] = dis[s]+1;
                Q.push(u);
            }
        }
    }
    return -1;
}

void init(int N, vector<int> a) {
    n = N; increasing = 1;
    stack<pair<int,int>> S;
    memset(pr,-1,sizeof(pr));
    memset(nx,-1,sizeof(nx));
    for(int i = 0; i < n; i++){
        increasing&=(!i or a[i]>=a[i-1]);
        while(!S.empty() and S.top().fi<a[i]) S.pop();
        if(!S.empty()) pr[i] = S.top().se;
        S.push({a[i],i});
    }
    while(!S.empty()) S.pop();
    for(int i = n-1; i>=0; i--){
        while(!S.empty() and S.top().fi<a[i]) S.pop();
        if(!S.empty()) nx[i] = S.top().se;
        S.push({a[i],i});
    }
    while(!S.empty()) S.pop();
    for(int i = 0; i < n; i++){
        if(pr[i]!=-1) adj[i].pb(pr[i]);
        if(nx[i]!=-1) adj[i].pb(nx[i]);
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if(increasing) return C-B;
    return bfs(A,B,C,D);
}

• Subtask 1: 4 / 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