제출 #1324675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324675		fr1tzy	밀림 점프 (APIO21_jumps)	C++20	컴파일 에러	0 ms	0 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
const int LOG = 18;
const int INF = 1e9;
int n;
int H[MAXN], pos[MAXN];
int leftg[MAXN], rightg[MAXN];
int up[LOG][MAXN];
int jumpl[LOG][MAXN];
int jumpr[LOG][MAXN];
int spa[LOG][MAXN];
int l[MAXN];
int range(int left, int right) {
  int k = l[right - left + 1];
  return max(spa[k][left], spa[k][right - (1 << k) + 1]);
}

void build() {
  for (int i = 1; i <= n; i++)
    spa[0][i] = H[i];

  for (int k = 1; k < LOG; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++)
      spa[k][i] = max(spa[k - 1][i], spa[k - 1][i + (1 << (k - 1))]);
}

void logs() {
  l[1] = 0;
  for (int i = 2; i <= n; i++)
    l[i] = l[i / 2] + 1;
}

void bng() {
  stack<int> s;
  H[0] = INF;
  s.push(0);
  for (int i = 1; i <= n; i++) {
    while (H[s.top()] <= H[i])
      s.pop();
    rightg[i] = s.top();
    s.push(i);
  }
}

void bbl() {
  for (int h = n; h >= 1; h--) {
    int i = pos[h];
    if (H[leftg[i]] > H[rightg[i]])
      up[0][i] = leftg[i];
    else
      up[0][i] = rightg[i];
  }
  for (int k = 1; k < LOG; k++)
    for (int i = 1; i <= n; i++)
      up[k][i] = up[k - 1][up[k - 1][i]];
  for (int i = 1; i <= n; i++) {
    jumpr[0][i] = rightg[i];
    jumpl[0][i] = leftg[i];
  }
  for (int k = 1; k < LOG; k++) {
    for (int i = 1; i <= n + 1; i++) {
      jumpr[k][i] = jumpr[k - 1][jumpr[k - 1][i]];
      jumpl[k][i] = jumpl[k - 1][jumpl[k - 1][i]];
    }
  }
}
void init(int N, vector<int> h) {
  n = N;
  for (int i = 1; i <= n; i++) {
    H[i] = h[i - 1];
    pos[H[i]] = i;
  }
  build();
  logs();
  bng();
  bbl();
}

int minimum(int A, int B, int C, int D) {
  A++;
  B++;
  C++;
  D++;
  int x = B;
  int maxt = range(C, D);
  int answer = 0;
  for (int k = LOG - 1; k >= 0; k--) {
    int nx = jumpl[k][x];
    if (nx >= A && H[nx] < maxt)
      x = nx;
  }
  while (true) {
    int nx = up[0][x];
    if (nx < C && rightg[x] < C && H[nx] < maxt) {
      x = nx;
      answer++;
    } else
      break;
  }
  for (int k = LOG - 1; k >= 0; k--) {
    int nx = jumpr[k][x];
    if (nx <= C) {
      x = nx;
      answer += (1 << k);
    }
  }
  if (x >= C && x <= D)
    return answer;
  if (rightg[x] >= C && rightg[x] <= D)
    return answer + 1;
  return -1;
}

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

/usr/bin/ld: /tmp/cc6fEKKY.o: in function `main':
stub.cpp:(.text.startup+0x1c1): undefined reference to `minimum_jumps(int, int, int, int)'
collect2: error: ld returned 1 exit status