Submission #1187366

#TimeUsernameProblemLanguageResultExecution timeMemory
1187366AvianshRainforest Jumps (APIO21_jumps)C++20
48 / 100
513 ms63308 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int maxn = 2e5+5; const int lg = 22; int h[maxn]; vector<int>g[maxn]; int rev[maxn]; int n; int opt[maxn][lg]; int nopt[maxn][lg]; struct segTree{ int *st; int n; vector<int>ar; void rupdate(int l, int r, int ind, int i){ if(i<l||i>r){ return; } if(l==r){ st[ind]=i; return; } int mid = (l+r)/2; rupdate(l,mid,ind*2+1,i); rupdate(mid+1,r,ind*2+2,i); if(ar[st[ind*2+1]]>ar[st[2*ind+2]]){ st[ind]=st[ind*2+1]; } else{ st[ind]=st[ind*2+2]; } } segTree(int siz, int arr[]){ int x = ceil(log2(siz)); x++; st=new int[(1<<x)]; fill(st,st+(1<<x),0); n=siz-1; for(int i = 0;i<siz;i++){ ar.push_back(arr[i]); } for(int i = 0;i<siz;i++){ rupdate(0,n,0,i); } } int rquery(int l, int r, int s, int e, int ind){ if(e<l||s>r){ return -1; } if(s<=l&&r<=e){ return st[ind]; } int mid = (l+r)/2; int lef = rquery(l,mid,s,e,ind*2+1); int rig = rquery(mid+1,r,s,e,ind*2+2); if(lef==-1){ return rig; } if(rig==-1){ return lef; } if(ar[lef]>ar[rig]){ return lef; } else{ return rig; } } int query(int l, int r){ return rquery(0,n,l,r,0); } }; segTree st(maxn,h); void init(int N, vector<int> H) { n=N; for(int i = 0;i<n;i++){ h[i]--; h[i]=H[i]; rev[h[i]-1]=i; } st=segTree(n,h); for(int i = 0;i<n;i++){ fill(opt[i],opt[i]+lg,i); fill(nopt[i],nopt[i]+lg,i); } set<int>inds; for(int i = n-1;i>=0;i--){ int ind = rev[i]; if(inds.size()){ auto it = inds.lower_bound(ind); int lef = -1; int rig = -1; if(it!=inds.end()){ g[ind].push_back(*it); rig=*it; } if(it!=inds.begin()){ it--; g[ind].push_back(*it); lef=*it; } if(lef==-1&&rig!=-1){ //opt and nopt both go right opt[ind][0]=rig; nopt[ind][0]=rig; for(int i = 1;i<lg;i++){ opt[ind][i]=opt[opt[ind][i-1]][i-1]; nopt[ind][i]=nopt[nopt[ind][i-1]][i-1]; } } if(lef!=-1&&rig==-1){ //opt and nopt both go right opt[ind][0]=lef; nopt[ind][0]=lef; for(int i = 1;i<lg;i++){ opt[ind][i]=opt[opt[ind][i-1]][i-1]; nopt[ind][i]=nopt[nopt[ind][i-1]][i-1]; } } if(lef!=-1&&rig!=-1){ //now must see if(h[lef]<h[rig]){ swap(lef,rig); } //now lef is opt rig is nopt opt[ind][0]=lef; nopt[ind][0]=rig; for(int i = 1;i<lg;i++){ opt[ind][i]=opt[opt[ind][i-1]][i-1]; nopt[ind][i]=nopt[nopt[ind][i-1]][i-1]; } } } inds.insert(rev[i]); } //graph creation done //kth ancestor shenanigans done } int minimum_jumps(int a, int b, int c, int d) { int ans = 0; //assert(a==b&&c==d); int leftmost = -1; if(g[c].size()){ int cu = *min_element(g[c].begin(),g[c].end()); if(cu<c) leftmost=cu; } leftmost++; a=max(a,leftmost); d=c; if(a>b) return -1; a=st.query(a,b); //assuming a=b,c=d //a will traverse rn for(int i = lg-1;i>=0;i--){ if(h[opt[a][i]]<h[c]){ ans+=(1<<i); a=opt[a][i]; } } if(a!=opt[a][0]){ if(h[opt[a][0]]<=h[c]){ ans++; a=opt[a][0]; } } //cout << "opt done\n"; //a is at best position, now nopts must occur for(int i = lg-1;i>=0;i--){ if(h[nopt[a][i]]<h[c]){ ans+=(1<<i); a=nopt[a][i]; } } if(a!=nopt[a][0]){ if(h[nopt[a][0]]<=h[c]){ ans++; a=nopt[a][0]; } } if(a!=c){ return -1; } //assert(ans!=0); assert(ans<n); return 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...