제출 #649908

#제출 시각아이디문제언어결과실행 시간메모리
649908ToroTN밀림 점프 (APIO21_jumps)C++14
4 / 100
1357 ms84752 KiB
#include "jumps.h" #include<bits/stdc++.h> using namespace std; #define X first #define Y second #include <vector> int n,h[200005],l[200005][25],r[200005][25],a,b,c,d,mx,node,cnt; int low[200005][25],high[200005][25],seg[800005],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 debug(int tree,int st,int ed) { int md=(st+ed)/2; if(st==ed) { printf("%d %d %d %d\n",tree,st,ed,seg[tree]); return; } debug(2*tree,st,md); debug(2*tree+1,md+1,ed); printf("%d %d %d %d\n",tree,st,ed,seg[tree]); } 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); //debug(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[r[j][i-1]][i-1]; low[j][i]=low[low[j][i-1]][i-1]; high[j][i]=high[high[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); node=b; if(r[node][0]>=c&&r[node][0]<=d)return 1; //printf("mx=%d\n",mx); //printf("%d\n",node); 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]; } } } //printf("%d %d\n",node,ans); ans=0; if(r[node][0]>=c&&r[node][0]<=d)return ans+1; for(int i=20;i>=0;i--) { if(high[node][i]!=0) { //printf("high=%d %d\n",i,high[node][i]); if(h[high[node][i]]<mx&&high[node][i]<c&&r[high[node][i]][0]<c&&r[high[node][i]][0]!=0) { node=high[node][i]; ans+=(1<<i); } } } //printf("%d %d\n",node,ans); node=high[node][0]; ans+=1; if(r[node][0]>=c&&r[node][0]<=d)return ans+1; for(int i=20;i>=0;i--) { if(low[node][i]!=0) { if(h[low[node][i]]<mx&&low[node][i]<c&&r[low[node][i]][0]<c&&r[low[node][i]][0]!=0) { node=low[node][i]; ans+=(1<<i); } } } //printf("%d %d\n",node,ans); node=low[node][0]; ans+=1; if(r[node][0]>=c&&r[node][0]<=d)return ans+1; 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...