Submission #1227790

#TimeUsernameProblemLanguageResultExecution timeMemory
1227790abdelhakimRainforest Jumps (APIO21_jumps)C++20
48 / 100
488 ms56872 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; ll maxn=2e5; vector<ll> tree(4*maxn+3); void update(ll node, ll l, ll r, ll pos, ll val) { if(pos < l || pos > r)return; if(l==r) { tree[node]=val; return; } ll mid=(l+r)/2; update(node*2+1,l,mid,pos,val); update(node*2+2,mid+1,r,pos,val); tree[node]=max(tree[node*2+1],tree[node*2+2]); } ll query(ll node, ll l, ll r, ll x, ll y) { if(max(l,x) > min(r,y))return 0; if(x<=l && r<=y)return tree[node]; ll mid=(l+r)/2; return max(query(node*2+1,l,mid,x,y),query(node*2+2,mid+1,r,x,y)); } 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; update(0,0,n-1,i,h[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] >= B) return -1; ll indd=A; if(mn[h[C]].first!=0) { indd=max(ind[mn[h[C]].first]+1,(ll)A); } ll cur=query(0,0,n-1,indd,B); ll ans=0; for (int j=19;j>=0;j--) { if(nqqz[cur][j]!=inf && nqqz[cur][j]<=h[C]) { cur=nqqz[cur][j]; ans+=1LL<<j; } } 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...