제출 #1117457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117457		lucascgar	밀림 점프 (APIO21_jumps)	C++17	4 / 100	1886 ms	23484 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=30;

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 (h[i]>n || h[i]<1){
            int a = 0, b = 5;
            long long ans = b/a%a;
        }
    }

    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
    int x = h[A], ds = h[C];

    int ans=0;
    for (int v=(1<<(MAXB-1)), i=MAXB-1;i>=0;i--,v>>=1) if (op[x][i]!=x && (i==0 || op[x][i]!=op[x][i-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]!=x && (i==0 || sb[x][i]!=sb[x][i-1])){
        if (sb[x][i]<=ds) x=sb[x][i], ans += v;
    }
    // cerr << "end " << x << ' ' << ans << '\n';
    if (x!=ds) return -1;
    return ans;

}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:34:23: warning: unused variable 'ans' [-Wunused-variable]
   34 |             long long ans = b/a%a;
      |                       ^~~

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