제출 #587738

#제출 시각아이디문제언어결과실행 시간메모리
587738krit3379밀림 점프 (APIO21_jumps)C++17
48 / 100
2554 ms36132 KiB
#include<bits/stdc++.h> #include"jumps.h" using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define N 200005 int t[4*N],arr[N],up[20][N],dow[20][N],n; void cre(int x,int l,int r){ if(l==r){t[x]=arr[l];return ;} int mid=(l+r)/2; cre(x*2,l,mid); cre(x*2+1,mid+1,r); t[x]=max(t[x*2],t[x*2+1]); } int sol(int x,int l,int r,int ll,int rr){ if(l>rr||ll>r||ll>rr)return 0; if(ll<=l&&r<=rr)return t[x]; int mid=(l+r)/2; return max(sol(x*2,l,mid,ll,rr),sol(x*2+1,mid+1,r,ll,rr)); } void init(int nn,vector<int> h){ int i,j,l,r,mid,val; n=nn; for(i=0;i<n;i++)arr[i+1]=h[i]; cre(1,1,n); arr[n+1]=n+1; for(i=0;i<20;i++)for(j=0;j<=n+1;j++)up[i][j]=dow[i][j]=n+1; for(i=1;i<=n;i++){ l=1,r=i-1; while(l<=r){ mid=(l+r)/2; if(sol(1,1,n,mid,i-1)>arr[i])dow[0][arr[i]]=arr[mid],l=mid+1; else r=mid-1; } l=i+1,r=n; while(l<=r){ mid=(l+r)/2; if(sol(1,1,n,i+1,mid)>arr[i])up[0][arr[i]]=arr[mid],r=mid-1; else l=mid+1; } if(up[0][arr[i]]<dow[0][arr[i]])swap(up[0][arr[i]],dow[0][arr[i]]); } for(i=1;i<20;i++)for(j=1;j<=n;j++){ up[i][j]=up[i-1][up[i-1][j]]; dow[i][j]=dow[i-1][dow[i-1][j]]; } return ; } int minimum_jumps(int a,int b,int c,int d){ a++,b++,c++,d++; int i,l,r,mid,ml,mm,mr,now,val,ans=0; mm=sol(1,1,n,b+1,c-1); mr=sol(1,1,n,c,d); if(mm>mr)return -1; l=c,r=d; while(l<=r){ mid=(l+r)/2; if(sol(1,1,n,c,mid)>mm)ml=arr[mid],r=mid-1; else l=mid+1; } l=a,r=b; now=n+1; while(l<=r){ mid=(l+r)/2; val=sol(1,1,n,mid,b); if(val<mr)now=val,r=mid-1; else l=mid+1; } if(now>mr)return -1; for(i=19;i>=0;i--)if(up[i][now]<ml)ans+=1<<i,now=up[i][now]; if(up[0][now]>=ml&&up[0][now]<=mr)return ans+1; for(i=19;i>=0;i--)if(dow[i][now]<ml)ans+=1<<i,now=dow[i][now]; if(dow[0][now]>=ml&&dow[0][now]<=mr)return ans+1; return -1; }

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:26:21: warning: unused variable 'val' [-Wunused-variable]
   26 |     int i,j,l,r,mid,val;
      |                     ^~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:78:5: warning: 'ml' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |     if(dow[0][now]>=ml&&dow[0][now]<=mr)return ans+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...