Submission #1114407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114407		lucascgar	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4008 ms	5088 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

/*
se eu tenho um cara da esquerda sempre vale pegar primeiro cara que der da direita
se eu tenho um destino na direita sempre vale pegar o maior cara da esquerda q chega la
nenhuma subtituição nos intervalos muda nada pq 
*/

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int MAXN = 2e5+10, MAXQ = 1e5+10, BIG = 1e9+8;

int n, h[MAXN];
int r[MAXN], l[MAXN];
bool thing = 0;
void init(int N, vector<int> H){
    n = N;
    thing = 1;
    for (int i=0;i<n;i++){
        h[i] = H[i], l[i]=r[i]=-1;
        if (h[i]!=i+1) thing=0;
    }

    if (thing) return;
    stack<int> ps;
    for (int i=0;i<n;i++){
        while (!ps.empty() && h[ps.top()]<h[i]){
            r[ps.top()]=i;
            ps.pop();
        }
        ps.push(i);
    }
    while (!ps.empty()) ps.pop();

    for (int i=n-1;i>=0;i--){
        while (!ps.empty() && h[ps.top()]<h[i]){
            l[ps.top()]=i;
            ps.pop();
        }
        ps.push(i);
    }

}
int minimum_jumps(int A, int B, int C, int D){  // A <= B < C <= D
    if (thing){
        return C-B;
    }
    int ans = BIG;
    vector<int> ds(n, -1);
    queue<int> q;
    for (int i=A;i<=B;i++){
        q.push(i);
        ds[i]=0;
    }

    while (!q.empty()){
        int u = q.front();
        q.pop();
        if (u>=C && u<=D){
            ans = ds[u];
            break;
        }
        if (l[u] != -1 && ds[l[u]]==-1){
            ds[l[u]] = ds[u]+1;
            q.push(l[u]);
        }
        if (r[u] != -1 && ds[r[u]]==-1){
            ds[r[u]] = ds[u]+1;
            q.push(r[u]);
        }
    }

    if (ans==BIG) return -1;
    return ans;

}

• 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