Submission #861781

#	Time	Username	Problem	Language	Result	Execution time	Memory
861781		NeroZein	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	820 ms	48068 KiB

jumps

#include "jumps.h"
#include "bits/stdc++.h" 

using namespace std; 

const int LOG = 18; 
const int N = 2e5 + 5; 

int a[N], id[N]; 
int l[N], r[N];
int lo[LOG][N], hi[LOG][N];

//   SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  void build(const vector<T>& arr, const F& f) {
    func = f; 
    n = static_cast<int>(arr.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = arr;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
}; 
SparseTable<int> spa;

void init(int N_, std::vector<int> H) {
  stack<int> stk;
  for (int i = 1; i <= N_; ++i) {
    a[i] = H[i - 1]; 
  }
  for (int i = 1; i <= N_; ++i) {
    while (!stk.empty() && a[stk.top()] < a[i]) {
      stk.pop();
    }
    if (!stk.empty()) {
      l[i] = stk.top();
    }
    stk.push(i);
  }
  while (!stk.empty()) {
    stk.pop();
  }
  for (int i = N_; i >= 1; --i) {
    while (!stk.empty() && a[stk.top()] < a[i]) {
      stk.pop();
    }
    if (!stk.empty()) {
      r[i] = stk.top();
    }
    stk.push(i);
    hi[0][i] = (a[l[i]] > a[r[i]] ? l[i] : r[i]);
    lo[0][i] = l[i] ^ r[i] ^ hi[0][i]; 
  }
  for (int j = 1; j < LOG; ++j) {
    for (int i = 1; i <= N_; ++i) {
      hi[j][i] = hi[j - 1][hi[j - 1][i]];
      lo[j][i] = lo[j - 1][lo[j - 1][i]]; 
    }
  }
  for (int i = 1; i <= N_; ++i) {
    id[a[i]] = i; 
  }
  vector<int> ord(N_);
  iota(ord.begin(), ord.end(), 1); 
  spa.build(ord, [&](int i, int j) {
    return a[i] > a[j] ? i : j;
  });
}

int go(int x, int y) {
  int ret = 0;
  for (int j = LOG - 1; j >= 0; --j) {
    if (hi[j][x] && a[hi[j][x]] <= a[y]) {
      //cout << x << ' ' << hi[j][x] << ' ' << a[x] << ' ' << a[hi[j][x]] << ' ' << j << '\n'; 
      x = hi[j][x]; 
      ret += 1 << j; 
    }
  }
  for (int j = LOG - 1; j >= 0; --j) {
    if (lo[j][x] && a[lo[j][x]] <= a[y]) {
      //cout << x << ' ' << hi[j][x] << ' ' << a[x] << ' ' << a[lo[j][x]] << ' ' << j << '\n'; 
      x = lo[j][x];
      ret += 1 << j; 
    }
  }
  return (x == y ? ret : -2); 
}

int minimum_jumps(int A, int B, int C, int D) {
  if (a[B + 1] > a[spa.get(C, D)]) {
    return -1;
  }
  int ih = spa.get(B, C - 1); 
  int bl = A, br = B;
  while (bl < br) {
    int mid = (bl + br) / 2;
    int cx = spa.get(mid, B); 
    if (a[cx] < a[ih]) {
      br = mid;
    } else {
      bl = mid + 1; 
    }
  }//bl is in H
  int iabx = spa.get(bl, B); 
  if (iabx == ih) {
    if (r[iabx] > C && r[iabx] <= D + 1) {
      return 1; 
    } else {
      return -1; 
    }
  }
  
  if (bl > A && r[bl] > C && r[bl] <= D + 1) {
    return 1;
  }
  int ans = (r[ih] && r[ih] <= D + 1 ? go(iabx, ih) + 1 : -1);
  //cout << iabx << ' ' << a[iabx] << ' ' << ih << ' ' << a[ih] << '\n'; 
  //cout << "ans: " << ans << '\n'; 
  if (a[spa.get(0, iabx)] > a[ih]) {
    bl = 0, br = iabx;
    while (bl < br) {
      int mid = (bl + br + 1) / 2;
      if (a[spa.get(mid, iabx)] > a[ih]) {
        bl = mid;
      } else {
        br = mid - 1; 
      }
    }
    if (r[bl + 1] && r[bl + 1] <= D + 1) {
      if (ans == -1) {
        ans = go(iabx, bl + 1) + 1;
      } else {
        ans = min(ans, go(iabx, bl + 1) + 1); 
      }
    }
  }
  return ans; 
}

• 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