Submission #1117472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117472		lucascgar	Rainforest Jumps (APIO21_jumps)	C++17	27 / 100	2130 ms	39620 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 

A=B e C=D:
    esquece esquerda e direita
    posso ir pro maior ou pro menor, pra toda decisão de ir pro menor o maior ainda é opção, ent sempre vale a pena enqunato puder ir maior, ir maior
    busca binária com sparse
*/

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, MAXB=22;

int n, h[MAXN];
int r[MAXN], l[MAXN];
int op[MAXN][MAXB], sb[MAXN][MAXB]; // optimal e suboptimal: op[i][j] = onde paro fazendo 2^j operações otimas partindo do elemento i
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+1]=r[i+1]=i+1;
        if (h[i]!=i+1) thing=0;
    }

    if (thing) return;

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

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

    for (int i=1;i<=n;i++){
        op[i][0] = max(l[i], r[i]);
        sb[i][0] = min(l[i], r[i]);
    }

    for (int j=1;j<MAXB;j++){
        for (int i=1;i<=n;i++){
            op[i][j] = op[op[i][j-1]][j-1], sb[i][j] = sb[sb[i][j-1]][j-1];
        }
    }

}
int minimum_jumps(int A, int B, int C, int D){  // A <= B < C <= D
    if (thing){
        return C-B;
    }
    if (A!=B || C!=D) return 0;
    // assume A=B and C=D
    // operações boas
    int st = h[A], ds = h[C], x = st;
    for (int i=MAXB-1;i>=0;i--) if (op[x][i]<=ds) x = op[x][i]; // achei ultimo até ds
    int ans=0;
    if (x!=st){
        for (int v=(1<<(MAXB-1)), i=MAXB-1;i>=0;i--,v>>=1) if (op[st][i]<x) st = op[st][i], ans+=v; // ultimo antes de x pra somar 1 depois

        st = op[st][0], ans++;
    }
    // "ruins"
    for (int i=MAXB-1;i>=0;i--) if (sb[x][i]<=ds) x = sb[x][i]; // achei ultimo até ds
    if (x!=st){
        for (int v=(1<<(MAXB-1)), i=MAXB-1;i>=0;i--,v>>=1) if (sb[st][i]<x) st = sb[st][i], ans+=v; // ultimo antes de x pra somar 1 depois
        st = sb[st][0], ans++;
    }


    // cerr << "end " << x << ' ' << ans << '\n';
    if (x!=ds) return -1;
    return ans;

}

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