Submission #1187296

#TimeUsernameProblemLanguageResultExecution timeMemory
1187296AvianshRainforest Jumps (APIO21_jumps)C++20
0 / 100
134 ms47400 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]; void init(int N, vector<int> H) { n=N; for(int i = 0;i<n;i++){ h[i]=H[i]; rev[h[i]-1]=i; } 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); a=b; d=c; //assuming a=b,c=d //a will traverse rn for(int i = lg-1;i>=0;i--){ if(h[opt[a][i]]>h[c]){ continue; } else{ if(i&&opt[a][i]==opt[a][i-1]) continue; if(i==0&&opt[a][i]==a) continue; ans+=(1<<i); assert(a!=opt[a][i]); a=opt[a][i]; //cout << "going to: " << a << " " << i << "\n"; } } //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]){ continue; } else{ if(i&&nopt[a][i]==nopt[a][i-1]) continue; if(i==0&&nopt[a][i]==a) continue; ans+=(1<<i); assert(a!=nopt[a][i]); a=nopt[a][i]; //cout << "going to: " << a << " " << i << "\n"; } } 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...