Submission #1228690

#TimeUsernameProblemLanguageResultExecution timeMemory
1228690abdelhakimRainforest Jumps (APIO21_jumps)C++20
48 / 100
579 ms96016 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; vector<vector<ll>> nqqz2; 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)); nqqz2.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]; } } } } } // tnqiza 2: for (int i=n;i>=1;i--) { for (int j=0;j<20;j++) { if(j==0) { if(mn[i].second!=0) { nqqz2[i][j]=mn[i].second; } } else { if(mn[i].second!=0) { ll x=nqqz2[i][j-1]; if(x!=inf) { nqqz2[i][j]=nqqz2[x][j-1]; } } } } } } int minimum_jumps(int A, int B, int C, int D) { ll kbir=query(0,0,n-1,C,D); if(mn[kbir].first!=0 && ind[mn[kbir].first] >= B) return -1; ll awal; if(mn[h[C]].first==0 || ind[mn[h[C]].first] < B) awal=h[C]; else awal=mn[h[C]].second; ll indd=A; if(mn[kbir].first!=0) { indd=max(ind[mn[kbir].first]+1,(ll)A); } ll cur=query(0,0,n-1,indd,B); if(cur > awal) return 1; ll ans=0; for (int j=19;j>=0;j--) { if(nqqz[cur][j]!=inf && nqqz[cur][j]<awal) { cur=nqqz[cur][j]; ans+=1LL<<j; } } if(mn[cur].second==awal) return ans+1; if(mn[cur].first < kbir) return ans+2; return ans + limn[cur]-limn[awal]; }
#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...