Submission #566883

#TimeUsernameProblemLanguageResultExecution timeMemory
566883TurkhuuRainforest Jumps (APIO21_jumps)C++17
0 / 100
1 ms208 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int inf = 1000000; int n; vector<int> a; vector<vector<int>> g; void init(int N, vector<int> H){ n = N; a = H; g.resize(n); for(int i = 0; i < n; i++){ int l = i - 1, r = i + 1; while(l >= 0 && a[l] <= a[i]) l--; while(r < n && a[r] <= a[i]) r++; if(l >= 0) g[i].push_back(l); if(r < n) g[i].push_back(r); } } int minimum_jumps(int A, int B, int C, int D){ queue<int> q; vector<int> d(n); for(int i = A; i <= B; i++){ d[i] = 0; q.push(i); } while(!q.empty()){ int i = q.front(); q.pop(); if(C <= i && i <= D){ return d[i]; } for(int j : g[i]){ if(d[i] + 1 < d[j]){ d[j] = d[i] + 1; q.push(j); } } } 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...