제출 #649870

#제출 시각아이디문제언어결과실행 시간메모리
649870ToroTN밀림 점프 (APIO21_jumps)C++14
0 / 100
312 ms38168 KiB
#include "jumps.h" #include<bits/stdc++.h> using namespace std; #define X first #define Y second #include <vector> int n,h[100005],l[100005][25],r[200005][25],a,b,c,d,mx,node,cnt; int low[100005][25],high[100005][25],seg[400005],ans; stack<pair<int,int> > stk; void build(int tree,int st,int ed) { int md=(st+ed)/2; if(st==ed) { seg[tree]=h[st]; return; } build(2*tree,st,md); build(2*tree+1,md+1,ed); seg[tree]=max(seg[2*tree],seg[2*tree+1]); } int query(int tree,int st,int ed,int l,int r) { int md=(st+ed)/2; if(st>r||ed<l)return -1e9; if(st>=l&&ed<=r)return seg[tree]; return max(query(2*tree,st,md,l,r),query(2*tree+1,md+1,ed,l,r)); } void init(int N, std::vector<int> H) { n=N; for(int i=1;i<=n;i++) { h[i]=H[i-1]; } build(1,1,n); for(int i=1;i<=n;i++) { while(!stk.empty()) { if(stk.top().X>h[i]) { break; }else { r[stk.top().Y][0]=i; stk.pop(); } } stk.push({h[i],i}); } while(!stk.empty()) { stk.pop(); } for(int i=n;i>=1;i--) { while(!stk.empty()) { if(stk.top().X>h[i]) { break; }else { l[stk.top().Y][0]=i; stk.pop(); } } stk.push({h[i],i}); } while(!stk.empty()) { stk.pop(); } for(int i=1;i<=n;i++) { if(l[i][0]!=0&&r[i][0]!=0) { low[i][0]=l[i][0]; high[i][0]=r[i][0]; if(h[l[i][0]]>h[r[i][0]])swap(low[i][0],high[i][0]); }else if(l[i][0]!=0||r[i][0]!=0) { low[i][0]=high[i][0]=max(l[i][0],r[i][0]); } } for(int i=1;i<=20;i++) { for(int j=1;j<=n;j++) { l[j][i]=l[l[j][i-1]][i-1]; r[j][i]=r[l[j][i-1]][i-1]; low[j][i]=low[l[j][i-1]][i-1]; high[j][i]=high[l[j][i-1]][i-1]; } } /*for(int j=0;j<=20;j++) { printf("%d\n",j); for(int i=1;i<=n;i++) { printf("%d ",r[i][j]); } printf("\n"); for(int i=1;i<=n;i++) { printf("%d ",l[i][j]); } printf("\n"); for(int i=1;i<=n;i++) { printf("%d ",low[i][j]); } printf("\n"); for(int i=1;i<=n;i++) { printf("%d ",high[i][j]); } printf("\n"); }*/ } int minimum_jumps(int A, int B, int C, int D) { a=A+1; b=B+1; c=C+1; d=D+1; mx=query(1,1,n,c,d); //printf("mx=%d\n",mx); node=b; for(int i=20;i>=0;i--) { if(l[node][i]!=0) { if(h[l[node][i]]<mx&&l[node][i]>=a) { node=l[node][i]; } } } ans=0; for(int i=20;i>=0;i--) { if(high[node][i]!=0) { if(h[high[node][i]]<mx&&high[node][i]<c) { node=high[node][i]; ans+=(1<<i); } } } //printf("afterhigh=%d\n",ans); //printf("%d\n",node); for(int i=20;i>=0;i--) { if(low[node][i]!=0) { if(h[low[node][i]]<mx&&low[node][i]<c) { node=low[node][i]; ans+=(1<<i); } } } //printf("afterlow=%d\n",ans); ans+=1; node=r[node][0]; if(node>=c&&node<=d) { return ans; } 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...