제출 #1215251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215251		loom	밀림 점프 (APIO21_jumps)	C++20	33 / 100	4053 ms	15448 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
#define nl '\n'

const int N = 2e5;
vector<int> g[N];
int n;

void add(vector<int> a, int x){
   vector<pair<int,int>> v;
   for(int i=0; i<n; i++){
      int ix = x ? n-i-1 : i;
      while(!v.empty() and v.back().first < a[i]) v.pop_back();
      if(!v.empty()) g[ix].push_back(v.back().second);
      v.push_back({a[i], ix});
   }
}

void init(int _n, vector<int> h){
   n = _n;

   add(h, 0);
   reverse(h.begin(), h.end());
   add(h, 1);
}

int minimum_jumps(int a, int b, int c, int d) {
   queue<int> q;
   vector<int> dist(n, -1);
   for(int i=a; i<=b; i++) q.push(i), dist[i] = 0;

   while(!q.empty()){
      int v = q.front();
      q.pop();

      if(c <= v and v <= d) return dist[v];

      for(int ch : g[v]){
         if(dist[ch] == -1){
            dist[ch] = dist[v]+1;
            q.push(ch);
         }
      }
   }

   return -1;
}

• 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