Submission #1227786

#TimeUsernameProblemLanguageResultExecution timeMemory
1227786abdelhakimRainforest Jumps (APIO21_jumps)C++20
0 / 100
3657 ms40140 KiB
#include "jumps.h" #include <bits/stdc++.h> #define ll long long #define inf (ll)(1e15) #define dbg(x) cerr <<#x << ' ' << x <<endl; using namespace std; ll n; vector<ll> h; vector<pair<ll,ll>> mn; vector<ll> ind; vector<ll> limn; vector<vector<ll>> nqqz; void init(int N, std::vector<int> H) { n=N; for (int i=0;i<n;i++) h.push_back(H[i]); mn.resize(n+1); stack<ll> s; for (int i=0;i<n;i++) { while(s.size() && (s.top() < h[i])) { s.pop(); } if(s.size()) { mn[h[i]].first=s.top(); } s.push(h[i]); } while(s.size())s.pop(); for (int i=n-1;i>=0;i--) { while(s.size() && (s.top() < h[i])) { s.pop(); } if(s.size()) { mn[h[i]].second=s.top(); } s.push(h[i]); } ind.resize(n+1); for (int i=0;i<n;i++) { ind[h[i]]=i; } limn.resize(n+1); for (int i=n-1;i>=0;i--) { if(mn[h[i]].second!=0) { limn[h[i]]=1+limn[mn[h[i]].second]; } } nqqz.assign(n+1,vector<ll>(20,inf)); for (int i=n;i>=1;i--) { for (int j=0;j<20;j++) { if(j==0) { if(max(mn[i].first,mn[i].second)!=0) { nqqz[i][j]=max(mn[i].first,mn[i].second); } } else { if(max(mn[i].first,mn[i].second)!=0) { ll x=nqqz[i][j-1]; if(x!=inf) { nqqz[i][j]=nqqz[x][j-1]; } } } } } } int minimum_jumps(int A, int B, int C, int D) { if(mn[h[C]].first!=0 && ind[mn[h[C]].first] >= A) return -1; ll cur=h[A]; ll ans=0; while(max(mn[cur].first,mn[cur].second)!=0) { ans++; cur=max(mn[cur].first,mn[cur].second); } return limn[cur]-limn[h[C]]+ans; }
#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...