Submission #948558

#	Time	Username	Problem	Language	Result	Execution time	Memory
948558		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4032 ms	5208 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S& a, const T& b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S& a, const T& b) {
	return a < b ? (a = b) == b : false;
}
const int inf = 1e9;

int n;
vector<int> h, l, r;
bool increasing = true;

void init(int N, std::vector<int> H) {
  n = N, h = H;
  for (int i = 1; i < n; ++i) {
    if (h[i] <= h[i - 1]) increasing = false;
  }
  l.resize(n), r.resize(n);
  iota(all(l), 0ll), iota(all(r), 0ll);
  stack<int> stk;
  for (int i = 0; i < n; ++i) {
    while (!stk.empty() && h[stk.top()] <= h[i]) {
      stk.pop();
    }
    if (!stk.empty()) l[i] = stk.top();
    stk.push(i);
  }
  while (!stk.empty()) stk.pop();
  for (int i = n - 1; i >= 0; --i) {
    while (!stk.empty() && h[stk.top()] <= h[i]) {
      stk.pop();
    }
    if (!stk.empty()) r[i] = stk.top();
    stk.push(i);
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  if (increasing) {
    return C - B;
  } else {
    vector<int> d(n, inf);
    queue<int> q;
    for (int i = A; i <= B; ++i) {
      q.push(i);
      d[i] = 0;
    }
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      if (chmin(d[l[v]], d[v] + 1)) {
        q.push(l[v]);
      }
      if (chmin(d[r[v]], d[v] + 1)) {
        q.push(r[v]);
      }
    }
    int res = inf;
    for (int i = C; i <= D; ++i) {
      chmin(res, d[i]);
    }
    return res == inf ? -1 : res;
  }
}

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