Submission #1060249

#TimeUsernameProblemLanguageResultExecution timeMemory
1060249alexddRainforest Jumps (APIO21_jumps)C++17
0 / 100
4037 ms17496 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int INF = 1e9; int parent[200005]; int anc[200005][18]; void init(int N, std::vector<int> H) { deque<int> dq; for(int i=N-1;i>=0;i--) { while(!dq.empty() && H[dq.back()] < H[i]) dq.pop_back(); if(dq.empty()) parent[i]=N; else parent[i]=dq.back(); dq.push_back(i); } parent[N]=N; for(int i=0;i<=N;i++) anc[i][0]=parent[i]; for(int p=1;p<18;p++) for(int i=0;i<=N;i++) anc[i][p] = anc[anc[i][p-1]][p-1]; } int getdist(int cur, int le, int ri) { int pasi=0; for(int p=17;p>=0;p--) { if(anc[cur][p]<le) { pasi += (1<<p); cur = anc[cur][p]; } } pasi++; cur = anc[cur][0]; if(cur>ri) return INF; return pasi; } int minimum_jumps(int A, int B, int C, int D) { int mnm=INF; for(int i=A;i<=B;i++) mnm = min(mnm, getdist(i,C,D)); if(mnm==INF) return -1; else return mnm; }
#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...