제출 #412967

#제출 시각아이디문제언어결과실행 시간메모리
412967AmineWeslati밀림 점프 (APIO21_jumps)C++14
81 / 100
2338 ms48236 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int>vi; #define pb push_back #define sz(v) (int)v.size() #define all(x) begin(x),end(x) typedef pair<int,int>pi; typedef vector<pi>vpi; #define fi first #define se second #define eb emplace_back #define FOR(i,a,b) for(int i=a; i<b; i++) #define ROF(i,a,b) for(int i=b-1; i>=a; i--) void ckmin(int &x, int y){x=min(x,y);} //---------------------- const ll INF=1e9; const int MX=2e5+10; const int LOG=25; int N; vi a(MX,INF); //---------- vi t(MX*4); int combine(int i, int j){ if(i==-1) return j; if(j==-1) return i; if(a[i]>=a[j]) return i; return j; } void build(int pos=1, int tl=1, int tr=N){ if(tl==tr){ t[pos]=tl; return; } int tm=(tl+tr)/2; build(pos*2,tl,tm); build(pos*2+1,tm+1,tr); t[pos]=combine(t[pos*2],t[pos*2+1]); } int get(int l, int r, int pos=1, int tl=1, int tr=N){ if(l>r) return -1; if(l==tl && r==tr) return t[pos]; int tm=(tl+tr)/2; return combine(get(l,min(r,tm),pos*2,tl,tm), get(max(tm+1,l),r,pos*2+1,tm+1,tr)); } //----------- int jump[MX][LOG],jumpRight[MX][LOG]; bool cmp(int i, int j){ return a[i]>a[j]; } vi lft,rgt; vi vec; void precompute(){ lft.assign(N+2,0); rgt.assign(N+2,N+1); vi st; FOR(i,1,N+1){ while(sz(st) && a[st.back()]<a[i]) st.pop_back(); if(sz(st)) lft[i]=st.back(); st.pb(i); } st.clear(); ROF(i,1,N+1){ while(sz(st) && a[st.back()]<a[i]) st.pop_back(); if(sz(st)) rgt[i]=st.back(); st.pb(i); } vec.resize(N); iota(all(vec),1); sort(all(vec),cmp); FOR(i,0,LOG){ jump[0][i]=0; jumpRight[0][i]=0; jump[N+1][i]=N+1; jumpRight[N+1][i]=N+1; } a[0]=a[N+1]=-1; for(int i: vec){ jumpRight[i][0]=rgt[i]; if(a[rgt[i]]>=a[lft[i]]) jump[i][0]=rgt[i]; else jump[i][0]=lft[i]; FOR(b,1,LOG){ jump[i][b]=jump[jump[i][b-1]][b-1]; jumpRight[i][b]=jumpRight[jumpRight[i][b-1]][b-1]; } } a[0]=a[N+1]=INF; reverse(all(vec)); } void init(int N, vi H){ ::N=N; FOR(i,0,N) a[i+1]=H[i]; build(); precompute(); } int cnt=0; int minimum_jumps(int A, int B, int C, int D){ A++; B++; C++; D++; //----------- cnt++; if((N<=2000 && cnt<=2000) || cnt<=5){ vi dp(N+2,INF); FOR(i,A,B+1) dp[i]=0; for(int i: vec){ ckmin(dp[rgt[i]],dp[i]+1); ckmin(dp[lft[i]],dp[i]+1); } int ans=INF; FOR(i,C,D+1) ckmin(ans,dp[i]); if(ans==INF) ans=-1; return ans; } /////////// int e=get(C,D),s; int l=1,r=e; while(l<=r){ int m=(l+r)/2; if(a[get(m,e)]<=a[e]){ s=m; r=m-1; } else l=m+1; } if(s>B) return -1; l=max(s,A); r=B; s=get(l,r); int ans=1; ROF(i,0,LOG) if(jump[s][i]<C && a[jump[s][i]]<=a[e]){ s=jump[s][i]; ans+=(1<<i); } ROF(i,0,LOG) if(jumpRight[s][i]<C){ s=jumpRight[s][i]; ans+=(1<<i); } return ans; }

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

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:148:17: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |  int e=get(C,D),s;
      |                 ^
#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...