ho un array (val è il segment tree di questo array) dove metto l’altezza del grattacielo più alto del percorso migliore da quel nodo fino alla fine poi semplicemente parto dall’ultimo nodo e faccio un update dei nodi man mano che li controllo, fallisco solo un testcase dell’ultima subtask ma non capisco proprio il motivo.
ecco il codice:
#define fai(x) for(int i=0;i<x;i++)
#define fop(a,b) for(int i=a;i<b;i++)
#define fom(a,b) for(int i=a;i>b;i--)
#define maxInt numeric_limits<int>::max()
#define pb push_back
#define MAXN 1000001
int val[4*MAXN];
int N;
void update(int v, int newVal){
val[N+v]=newVal;
for(int i = (N+v)/2;i>0; i/=2) val[i]=min(val[i*2],val[i*2+1]);
}
int find(int a, int b){
a+=N; b+=N;
int res=maxInt;
while(a<=b) {
if(a%2) res= min(res,val[a++]);
if (b%2 == 0)res = min(res,val[b--]);
a /= 2; b /= 2;
}
return res;
}
int salta(int N, vector<int> S, vector<int> A, vector<int> B){
::N=N+1; S.pb(0); A.pb(0); B.pb(0);
fom(2*N+1,N)
val[i]=S[i];
fom(N,0)
val[i]=min(val[2*1],val[2*i+1]);
fom(N,-1){
int temp = find(i+A[i],i+B[i]);
val[i]=max(S[i],temp);
update(i,val[i]);
//cout<<i<<" "<<val[i]<<"\n";
}
return val[0];
}