Submission #572300

#	Time	Username	Problem	Language	Result	Execution time	Memory
572300		600Mihnea	밀림 점프 (APIO21_jumps)	C++17	0 / 100	4051 ms	4380 KiB

jumps

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

using namespace std;


const int N = 200000 + 7;
const int inf = (int) 1e9 + 7;
int n, a[N], lft[N], rgh[N];

void init(int nn, vector<int> hh) {
  n = nn;

  assert(n == (int) hh.size());

  for (int i = 1; i <= n; i++) {
    a[i] = hh[i - 1];
  }

  {
    vector<int> stk;
    for (int i = 1; i <= n; i++) {
      while (!stk.empty() && a[stk.back()] <= a[i]) stk.pop_back();
      if (!stk.empty()) lft[i] = stk.back(); else lft[i] = 0;
      stk.push_back(i);
    }
  }
  {
    vector<int> stk;
    for (int i = n; i >= 1; i--) {
      while (!stk.empty() && a[stk.back()] <= a[i]) stk.pop_back();
      if (!stk.empty()) rgh[i] = stk.back(); else rgh[i] = 0;
      stk.push_back(i);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (lft[i]) {
      assert(a[lft[i]] > a[i]);
    }
    if (rgh[i]) {
      assert(a[rgh[i]] > a[i]);
    }
  }
}

int minimum_jumps(int l1, int r1, int l2, int r2) {
  l1++;
  r1++;
  l2++;
  r2++;

  assert(1 <= l1 && l1 <= r1 && r1 < l2 && l2 <= r2 && r2 <= n);

  int sol = inf;
  int y = max_element(a + l2, a + r2 + 1) - a;

  for (int x = l1; x <= r1; x++) {
    assert(x <= y);
    int mx = 0;
    for (int j = x + 1; j < y; j++) {
      mx = max(mx, a[j]);
    }
    if (mx > a[y]) continue;
    if (a[x] > a[y]) continue;
    int p = x, cost = 0;
    while (p != y) {

      assert(a[p] <= a[y]);

      int p2 = p;
      if (lft[p] && a[lft[p]] <= a[y] && a[lft[p]] > a[p2]) p2 = lft[p];
      if (rgh[p] && a[rgh[p]] <= a[y] && a[rgh[p]] > a[p2]) p2 = rgh[p];

      assert(p2 != p);
      assert(a[p] < a[p2]);
      p = p2;
      cost++;

    }
    assert(p == y);
    sol = min(sol, cost);

  }

  if (sol == inf) {
    sol = -1;
  }

  return sol;
}

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