제출 #412961

#제출 시각아이디문제언어결과실행 시간메모리
412961AmineWeslati밀림 점프 (APIO21_jumps)C++14
48 / 100
2590 ms48200 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--) //---------------------- 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]; } void precompute(){ vi lft(N+2,0),rgt(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); } vi vec(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; } void init(int N, vi H){ ::N=N; FOR(i,0,N) a[i+1]=H[i]; build(); precompute(); } int minimum_jumps(int A, int B, int C, int D){ A++; B++; C++; D++; 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); //---------- l=C; r=e; while(l<=r){ int m=(l+r)/2; if(get(C,m)>=a[s]){ e=m; r=m-1; } else l=m+1; } //------------ 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:122:17: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |  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...