제출 #1117504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117504		lucascgar	밀림 점프 (APIO21_jumps)	C++17	27 / 100	2113 ms	39504 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

/*
vai pegar 27/100
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]);
        if (op[i][0] == i) op[i][0]=BIG;
        if (sb[i][0]==i) sb[i][0]=BIG;
    }

    for (int j=1;j<MAXB;j++){
        for (int i=1;i<=n;i++){
            if (op[i][j-1]==BIG) op[i][j]=BIG;
            else op[i][j] = op[op[i][j-1]][j-1];
            if (sb[i][j-1]==BIG) sb[i][j]=BIG;
            else 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;
    int ans=0;

    for (int v=(1<<(MAXB-1)), i=MAXB-1;i>=0;i--,v>>=1){
        if (op[x][i]<=ds) x = op[x][i],ans+=v;
    }
 
    for (int v=(1<<(MAXB-1)), i=MAXB-1;i>=0;i--,v>>=1){
        if (sb[x][i]<=ds) x=sb[x][i], ans += v;
    }


    // 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