제출 #1274463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274463		altern23	밀림 점프 (APIO21_jumps)	C++20	100 / 100	419 ms	49724 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 2e5;
const int INF = 1e9;

int kiri[MAXN + 5][20], kanan[MAXN + 5][20], best[MAXN + 5][20];
int H[MAXN + 5];

void init(int N, vector<int> h) {
  H[0] = INF;
  for(int i = 1; i <= N; i++) H[i] = h[i - 1];
  H[N + 1] = INF;
  
  for(int i = 1; i <= N; i++){
    kiri[i][0] = i - 1;
    while(H[kiri[i][0]] < H[i]) kiri[i][0] = kiri[kiri[i][0]][0];
    for(int j = 1; j < 20; j++) kiri[i][j] = kiri[kiri[i][j - 1]][j - 1];    
  }
  
  for(int j = 0; j < 20; j++) kanan[N + 1][j] = N + 1;
  for(int i = N; i >= 1; i--){
    kanan[i][0] = i + 1;
    while(H[kanan[i][0]] < H[i]) kanan[i][0] = kanan[kanan[i][0]][0];
    for(int j = 1; j < 20; j++) kanan[i][j] = kanan[kanan[i][j - 1]][j - 1];    
  }
  
  for(int i = 1; i <= N; i++){
    if(H[kiri[i][0]] > H[kanan[i][0]]) best[i][0] = kiri[i][0];
    else best[i][0] = kanan[i][0];
  }
  
  for(int j = 1; j < 20; j++){
    for(int i = 1; i <= N; i++) best[i][j] = best[best[i][j - 1]][j - 1];
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  A++, B++, C++, D++;
  
  int now = B;
  for(int j = 19; j >= 0; --j){
    if(kanan[now][j] < C){
      now = kanan[now][j];
    }
  }
  C = kanan[now][0];
  
  if(C > D){
    return -1;
  }
  
  now = C;
  for(int j = 19; j >= 0; --j){
    if(kanan[now][j] <= D){
      now = kanan[now][j];
    }
  }
  D = now;
  
  now = B;
  for(int j = 19; j >= 0; --j){
    if(H[kiri[now][j]] < H[D] && kiri[now][j] >= A){
      now = kiri[now][j];
    }
  }
  
  int ans = 0;
  for(int j = 19; j >= 0; --j){
    if(H[best[now][j]] < H[C]){
      ans += (1LL << j);
      now = best[now][j];
    }
  }
  
  if(kanan[now][0] >= C) return ans + 1;
  else if(kiri[now][0] && kanan[kiri[now][0]][0] <= D) return ans + 2;
  
  for(int j = 19; j >= 0; --j){
    if(kanan[now][j] < C){
      ans += (1LL << j);
      now = kanan[now][j];
    }
  }
  
  return ans + 1;
}

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