제출 #981277

#제출 시각아이디문제언어결과실행 시간메모리
981277Jawad_Akbar_JJ밀림 점프 (APIO21_jumps)C++17
33 / 100
4057 ms16672 KiB
#include "jumps.h" #include <iostream> #include <vector> #include <queue> using namespace std; const int N = 2e5 + 10; vector<int> nei[N]; int lft[N]; int rgt[N]; int Mn[N]; int seen[N]; void init(int n,vector<int> h){ vector<int> v; for (int i=0;i<n;i++) lft[i] = rgt[i] = -1; for (int i=0;i<n;i++){ while (v.size() > 0 and h[v.back()] < h[i]) rgt[v.back()] = i,v.pop_back(); v.push_back(i); } v.clear(); for (int i=n-1;i>=0;i--){ while (v.size() > 0 and h[v.back()] < h[i]) lft[v.back()] = i,v.pop_back(); v.push_back(i); } for (int i=0;i<n;i++){ if (lft[i] != -1) nei[i + 1].push_back(lft[i] + 1); if (rgt[i] != -1) nei[i + 1].push_back(rgt[i] + 1); } } int cur = 0; int minimum_jumps(int A, int B, int C, int D) { cur++; queue<int> Q; for (int i=A+1;i<=B + 1;i++) Q.push(i),seen[i] = cur,Mn[i] = 0; while (!Q.empty()){ int u = Q.front(); if (u >= C+1 and u <= D+1) return Mn[u]; Q.pop(); for (int i : nei[u]) if (seen[i] != cur) Mn[i] = Mn[u] + 1,Q.push(i),seen[i] = cur; } return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...