제출 #1113134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113134		ortsac	밀림 점프 (APIO21_jumps)	C++17	33 / 100	4062 ms	14136 KiB

jumps

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

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

int n;
vector<int> h;
vector<int> l;
vector<int> r;

void init(int32_t N, vector<int32_t> H) {
  n = N;
  h.resize(n);
  for (int i = 0; i < n; i++) h[i] = H[i];
  l.resize(n);
  r.resize(n);
  stack<pii> s;
  for (int i = 0; i < n; i++) {
    while (!s.empty() && (s.top().fr < h[i])) s.pop();
    if (s.empty()) l[i] = -1;
    else l[i] = s.top().se;
    s.push({h[i], i});
  }
  while (!s.empty()) s.pop();
  for (int i = n - 1; i >= 0; i--) {
    while (!s.empty() && (s.top().fr < h[i])) s.pop();
    if (s.empty()) r[i] = -1;
    else r[i] = s.top().se;
    s.push({h[i], i});
  }
  //for (int i = 0; i < n; i++) cout << l[i] << " " << r[i] << "\n";
  return;
}

const int INF = 0x3f3f3f3f;

vector<int> dist;

int calc(int node) {
  //cout << "node " << node << "\n";
  if (node == -1) return INF;
  if (dist[node] != INF) return dist[node];
  dist[node] = min(calc(l[node]) + 1, calc(r[node]) + 1);
  return dist[node];
}

int32_t minimum_jumps(int32_t A, int32_t B, int32_t C, int32_t D) {
  dist.clear();
  dist.resize(n, INF);
  for (int i = C; i <= D; i++) dist[i] = 0;
  int ans = INF;
  for (int i = A; i <= B; i++) {
    ans = min(ans, calc(i));
  }
  if (ans == INF) return -1;
  else return ans;
}

• Subtask 1: 0 / 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