Submission #1199049

#TimeUsernameProblemLanguageResultExecution timeMemory
1199049origabaiRainforest Jumps (APIO21_jumps)C++20
0 / 100
88 ms34052 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; int N; vector<int> H; int lg; vector<vector<int>> out; vector<vector<int>> mn,mx; void init(int N2, std::vector<int> H2){ N=N2; H=H2; stack<int> s; out.resize(N); for (int i=0;i<N;i++){ while (s.size() && H[s.top()] < H[i]){ out[s.top()].push_back(i); s.pop(); } s.push(i); } while (s.size()) s.pop(); for (int i=N-1;i>=0;i--){ while (s.size() && H[s.top()] < H[i]){ out[s.top()].push_back(i); s.pop(); } s.push(i); } lg = log2(N) + 1; mx.resize(lg); mn.resize(lg); for (int i=0;i<lg;i++){ mx[i].resize(N); mn[i].resize(N); } for (int i=0;i<N;i++){ if (out[i].size() == 1){ mx[0][i] = mn[0][i] = out[i][0]; } else if (out[i].size() == 2){ int a = out[i][0], b = out[i][1]; if (H[a] > H[b]) swap(a,b); mn[0][i] = a; mx[0][i] = b; } else { mn[0][i] = mx[0][i] = i; } } for (int i=1;i<lg;i++){ for (int j=0;j<N;j++){ mx[i][j] = mx[i-1][mx[i-1][j]]; mn[i][j] = mn[i-1][mn[i-1][j]]; } } } int minimum_jumps(int A, int B, int C, int D) { int ans = 0; for (int k=lg-1;k>=0;k--){ if (H[mx[k][A]] < H[C]){ A = mx[k][A]; ans += (1 << k); } } for (int k=lg-1;k>=0;k--){ if (H[mn[k][A]] < H[C]){ A = mn[k][A]; ans += (1 << k); } } if (mn[0][A] == C || mx[0][A] == C){ return ans+1; } 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...