Submission #1161756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161756		fryingduc	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	478 ms	48212 KiB

jumps

#include "jumps.h"

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "D:\\debug.h"
#else 
#define debug(...)
#endif 

namespace {
  const int maxn = 2e5 + 5;
  const int LG = 18;
  int n;
  int h[maxn];
  int sl[maxn][LG + 1], sr[maxn][LG + 1];
  int nxt[maxn][LG + 1];
}

void init(int N, std::vector<int> H) {
  n = N;
  for (int i = 1; i <= n; ++i) {
    h[i] = H[i - 1];
  }
  stack<int> st;
  for (int i = 1; i <= n; ++i) {
    while (!st.empty() and h[st.top()] < h[i]) {
      st.pop();
    }
    sl[i][0] = st.empty() ? 0 : st.top();
    st.push(i);
  }
  st = stack<int>();
  for (int i = n; i; --i) {
    while (!st.empty() and h[st.top()] < h[i]) {
      st.pop();
    }
    sr[i][0] = st.empty() ? 0 : st.top();
    st.push(i);
  }
  for (int i = 1; i <= n; ++i) {
    nxt[i][0] = (sr[i][0] == 0 || h[sr[i][0]] < h[sl[i][0]] ? sl[i][0] : sr[i][0]);
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i <= n + 1; ++i) {
      sl[i][j] = sl[sl[i][j - 1]][j - 1];
      sr[i][j] = sr[sr[i][j - 1]][j - 1];
      nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
    }
  }
}

int get(int l, int r) {
  if (l > r) return 0;
  int cur = l;
  for (int i = LG; i >= 0; --i) {
    if (sr[cur][i] and sr[cur][i] <= r) {
      cur = sr[cur][i];
    }
  }
  return cur;
}

int minimum_jumps(int A, int B, int C, int D) {
  int a = A + 1, b = B + 1, c = C + 1, d = D + 1;
  int m = h[get(c, d)];
  int mx = h[get(b + 1, c - 1)];
  int opt = b;
  for (int i = LG; i >= 0; --i) {
    if (sl[opt][i] >= a and h[sl[opt][i]] < m) {
      opt = sl[opt][i];
    }
  }
  int en = b;
  for (int i = LG; i >= 0; --i) {
    if (sr[en][i] and sr[en][i] < c) {
      en = sr[en][i];
    }
  }
  en = sr[en][0];
  if (en > d) {
    return -1;
  }
  int res = 0;  
  for (int i = LG; i >= 0; --i) {
    if (nxt[opt][i] and h[nxt[opt][i]] < h[en]) {
      res += (1 << i);
      opt = nxt[opt][i];
    }
  }
  if (sr[opt][0] >= c and sr[opt][0] <= d) {
    return res + 1;
  }
  if (sl[opt][0] and sr[sl[opt][0]][0] >= c and sr[sl[opt][0]][0] <= d) {
    return res + 2;
  }
  for (int i = LG; i >= 0; --i) {
    if (sr[opt][i] and sr[opt][i] < c) {
      res += (1 << i);
      opt = sr[opt][i];
    }
  }
  if (sr[opt][0] >= c and sr[opt][0] <= d) {
    return res + 1;
  }
  
  return -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