SRM 647 Div2 Hard

問題

各成分が0以上の成分であるa[i](1<=i<=N)を以下の条件を満たすように定めたい。
1. | a[i] - a[i+1] | <= K
2. a[x[i]] <= t[i]
取りうる数列の最大値を求めよ.
ただし
N<=10^9くらい
size(x) = size(t) <= min(500,N)

解法

xとtのサイズが小さいのでa[x[i]]から傾きKの直線を弾いて交差するものを縮め、それを逆向きにもやって更新がなくなるまで続けた後に最大の高さを求めるみたいなことをやる。