Submission #1324729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324729		fr1tzy	Rainforest Jumps (APIO21_jumps)	C++20	Compilation error	0 ms	0 KiB

jumps

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

static const int MAXN = 200000 + 5;
static const int LG = 19;

int N, Q;
int H[MAXN];
int Lv[MAXN], Rv[MAXN];
int upHigh[MAXN][LG];
int upR[MAXN][LG];
int idx[MAXN];
int lg2[MAXN];
int stMax[MAXN][LG];

int rangeMax(int l, int r) {
  if (l > r)
    return 0;
  int j = lg2[r - l + 1];
  return max(stMax[l][j], stMax[r - (1 << j) + 1][j]);
}

void init_structures(const vector<int> &h0) {
  N = (int)h0.size();
  for (int i = 1; i <= N; i++)
    H[i] = h0[i - 1];
  vector<int> st;
  for (int i = 1; i <= N; i++) {
    while (!st.empty() && H[st.back()] < H[i]) {
      Rv[st.back()] = i;
      st.pop_back();
    }
    if (!st.empty())
      Lv[i] = st.back();
    st.push_back(i);
  }
  H[0] = INT_MAX;
  for (int i = 1; i <= N; i++) {
    int L = Lv[i], R = Rv[i];
    if (L == 0)
      upHigh[i][0] = R;
    else if (R == 0)
      upHigh[i][0] = L;
    else {
      upHigh[i][0] = (H[L] > H[R]) ? L : R;
    }
    upR[i][0] = Rv[i];
  }

  for (int j = 1; j < LG; j++) {
    for (int i = 1; i <= N; i++) {
      upHigh[i][j] = upHigh[upHigh[i][j - 1]][j - 1];
      upR[i][j] = upR[upR[i][j - 1]][j - 1];
    }
  }
  for (int i = 1; i <= N; i++)
    idx[H[i]] = i;
  lg2[1] = 0;
  for (int i = 2; i < MAXN; i++)
    lg2[i] = lg2[i / 2] + 1;

  for (int i = 1; i <= N; i++)
    stMax[i][0] = H[i];
  for (int j = 1; j < LG; j++) {
    for (int i = 1; i + (1 << j) - 1 <= N; i++) {
      stMax[i][j] = max(stMax[i][j - 1], stMax[i + (1 << (j - 1))][j - 1]);
    }
  }
}

int minimum_jumps_query(int A, int B, int C, int D) {
  A++, B++, C++, D++;

  int X = rangeMax(B, C - 1);
  int Y = rangeMax(C, D);
  if (X > Y)
    return -1;

  int l = A, r = B;
  int chosenHeight = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    int mx = rangeMax(mid, B);
    if (mx < Y) {
      chosenHeight = mx;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  int u = idx[chosenHeight];
  int res = 0;
  for (int j = LG - 1; j >= 0; j--) {
    int v = upHigh[u][j];
    if (v && H[v] < X) {
      u = v;
      res += 1 << j;
    }
  }
  if (Rv[u] >= C)
    return res + 1;
  if (upHigh[u][0] && H[upHigh[u][0]] < Y)
    return res + 2;

  for (int j = LG - 1; j >= 0; j--) {
    int v = upR[u][j];
    if (v && v < C) {
      u = v;
      res += 1 << j;
    }
  }
  return res + 1;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N >> Q;
  vector<int> h(N);
  for (int i = 0; i < N; i++)
    cin >> h[i];

  init_structures(h);

  while (Q--) {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << minimum_jumps_query(A, B, C, D) << "\n";
  }
  return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc539xqi.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccdUBXRV.o:jumps.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc539xqi.o: in function `main':
stub.cpp:(.text.startup+0x159): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: stub.cpp:(.text.startup+0x1c1): undefined reference to `minimum_jumps(int, int, int, int)'
collect2: error: ld returned 1 exit status