제출 #1189007

#제출 시각아이디문제언어결과실행 시간메모리
1189007AvianshRainforest Jumps (APIO21_jumps)C++20
4 / 100
617 ms97732 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]; int l[maxn][lg]; int r[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,-1); fill(nopt[i],nopt[i]+lg,-1); fill(l[i],l[i]+lg,-1); fill(r[i],r[i]+lg,-1); } 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; } l[ind][0]=lef; r[ind][0]=rig; for(int i = 1;i<lg;i++){ if(l[ind][i-1]!=-1){ l[ind][i]=l[l[ind][i-1]][i-1]; } else{ l[ind][i]=-1; } if(r[ind][i-1]!=-1){ r[ind][i]=r[r[ind][i-1]][i-1]; } else{ r[ind][i]=-1; } } 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++){ if(opt[ind][i-1]!=-1){ opt[ind][i]=opt[opt[ind][i-1]][i-1]; } if(nopt[ind][i-1]!=-1) nopt[ind][i]=nopt[nopt[ind][i-1]][i-1]; } } if(lef!=-1&&rig==-1){ //opt and nopt both go left opt[ind][0]=lef; nopt[ind][0]=lef; for(int i = 1;i<lg;i++){ if(opt[ind][i-1]!=-1){ opt[ind][i]=opt[opt[ind][i-1]][i-1]; } if(nopt[ind][i-1]!=-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++){ if(opt[ind][i-1]!=-1){ opt[ind][i]=opt[opt[ind][i-1]][i-1]; } if(nopt[ind][i-1]!=-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; if(b==c-1){ if(r[b][0]<=d&&r[b][0]!=-1){ return 1; } else{ return -1; } } int middle_max = st.query(b+1,c-1); //cout << "middle max: " << middle_max << "\n"; int s = b; for(int i = lg-1;i>=0;i--){ if(l[s][i]>=a&&h[l[s][i]]<h[middle_max]){ s=l[s][i]; } } //cout << "s: " << s << "\n"; int cur = s; //cur -> midmax -> c-d //cur -> smth>midmax -> c-d //smth is basically try to reach midmax with opt then go left and right again for(int i = lg-1;i>=0;i--){ int nx = opt[cur][i]; if(nx!=-1&&h[nx]<h[middle_max]){ cur=nx; //cout << "gone to: " << cur << "\n"; ans+=(1<<i); //cout << "h\n"; } } if(opt[cur][0]==middle_max){ ans++; cur=opt[cur][0]; } int temp = 1e9; if(l[cur][0]!=-1&&r[l[cur][0]][0]!=-1&&r[l[cur][0]][0]<=d){ temp=ans+2; } for(int i = lg-1;i>=0;i--){ int nx = nopt[cur][i]; if(nx<c&&nopt[cur][i]!=cur&&nopt[cur][i]!=-1){ cur=nx; //cout << "here " << i << " " << nx << "\n"; ans+=(1<<i); } } cur=nopt[cur][0]; ans++; if(cur>=c&&cur<=d){ return min(ans,temp); } return -1; }
#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...