Submission #1059290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059290		VMaksimoski008	Rainforest Jumps (APIO21_jumps)	C++17	60 / 100	4027 ms	67016 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5 + 5;
 
int n, L[maxn][20], R[maxn][20], up[maxn][20], up2[maxn][20], sub1 = 1;
vector<int> v;
 
void init(int N, vector<int> H) {
    n = N;
    v.push_back(1e9);
    for(int &x : H) v.push_back(x);
    v.push_back(1e9);
 
    stack<pair<int, int> > st; st.push({ 1e9, 0 });
    for(int i=1; i<=n; i++) {
        if(v[i] != i) sub1 = 0;
        while(!st.empty() && st.top().first <= v[i]) st.pop();
        L[i][0] = st.top().second;
        st.push({ v[i], i });
    }
 
    while(!st.empty()) st.pop();
 
    st.push({ 1e9, n + 1 });
    for(int i=n; i>=1; i--) {
        while(!st.empty() && st.top().first <= v[i]) st.pop();
        R[i][0] = st.top().second;
        st.push({ v[i], i });
    }
 
    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++) L[i][j] = L[L[i][j-1]][j-1];
    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++) R[i][j] = R[R[i][j-1]][j-1];
 
    for(int i=1; i<=n; i++) {
        if(L[i][0] == 0 && R[i][0] == n+1) up[i][0] = 0;
        else if(L[i][0] == 0) up[i][0] = up2[i][0] = R[i][0];
        else if(R[i][0] == 0) up[i][0] = up2[i][0] = L[i][0];
        else {
            up[i][0] = (v[L[i][0]] >= v[R[i][0]] ? L[i][0] : R[i][0]);
            up2[i][0] = (v[L[i][0]] >= v[R[i][0]] ? R[i][0] : L[i][0]);
        }
    }
 
    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++) up[i][j] = up[up[i][j-1]][j-1];
    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++) up2[i][j] = up2[up2[i][j-1]][j-1];
}
 
int minimum_jumps(int A, int B, int C, int D) {
    if(sub1) return C - B;
    A++; B++; C++; D++;
 
    if(A == B && C == D) {
        if(v[A] > v[C]) return -1;
        int ans = 0;
 
        for(int i=19; i>=0; i--) {
            if(up[A][i] == 0) continue;
            if(v[up[A][i]] <= v[C]) ans += (1 << i), A = up[A][i];
        }
 
        if(v[A] > v[C]) return -1;
 
        for(int i=19; i>=0; i--) {
            if(up2[A][i] == 0) continue;
            if(v[up2[A][i]] <= v[C]) ans += (1 << i), A = up2[A][i];
        }
 
        if(L[A][0] == C || R[A][0] == C) return ans + 1;
        return (A == C ? ans : -1);
    }
 
    vector<int> dist(n+1), vis(n+1);
    queue<int> q;
 
    for(int i=A; i<=B; i++) vis[i] = 1, q.push(i);
 
    while(!q.empty()) {
        int u = q.front();
        q.pop();
 
        if(C <= u && u <= D) return dist[u];
 
        if(L[u][0] != 0 && !vis[L[u][0]]) {
            vis[L[u][0]] = 1;
            dist[L[u][0]] = dist[u] + 1;
            q.push(L[u][0]);
        }
 
        if(R[u][0] != n + 1 && !vis[R[u][0]]) {
            vis[R[u][0]] = 1;
            dist[R[u][0]] = dist[u] + 1;
            q.push(R[u][0]);
        }
    }
 
    return -1;
}

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