ARC 082 F. Sandglass
問題
F: Sandglass - AtCoder Regular Contest 082 | AtCoder
問題概要
容量Xの砂時計にはじめaだけ砂が入っている。時刻riに砂時計をひっくり返すとき、時刻tにおいて砂時計（の片側）に残っている砂の量はいくらか。(t, a)がクエリとして与えられるのでQ回答えよ。
方針
f(t):=時刻tにおいて砂時計（のパーツA）に残っている砂の量 としてグラフを考えてみます。f(0)=ajとすると各クエリにはf(tj)と答えられます。
砂が無限にあるときは、グラフがギザギザするだけなので簡単です。（f(0)+砂の増減とすればいいです）
実際は砂が落ちきることがあるので、＼＿／←こうなるところがあります。なので単純に増減分だけ調整すればいいことにはなりません。
クエリの数だけ（初期状態の異なる）砂時計が存在すると考えると、f(t)のグラフがQ個かけます。異なる砂時計でも砂の落ちる速さは一定なので、それぞれのグラフの大小が逆転することはありません（初期値f(0)=ajでの大小が保たれます）。つまり、f(0)=aj, akに対するfをそれぞれfj, fkとすると、fj(0)<fk(0)だがある時刻tでfj(t)>fk(t)となることはありません。fj(t)=fk(t)となりうることに注意します。これは、上に挙げたように砂が落ちきることがあるからです。また、ひとたびfj(t)=fk(t)となったとすると以降のτ≧tでfj(τ)=fk(τ)が成り立ちます。
初期値の最小・最大は0, Xなので全てのグラフはf(0)=0, Xで定まる2つのグラフに挟まれることが分かります。それぞれの時刻tにおける値をl(t), u(t)とします。クエリ(aj, tj)に答えるには、f(0)=ajとしてf(tj)が分かればいいのでした。f(tj)の値として考えられるのは、l(tj), u(tj), f(0)+(tjまでの砂の増減)の3つです。f(0)+(増減)<l(tj)のとき、f(tj)=f(0)+(増減)は不適なのでf(tj)=l(tj)になりそうです（きっとなります）。u(tj)のときも同様でです。l(tj)<f(0)+(増減)<u(tj)のとき、イライラ棒を抜けてきた感じがするのでf(tj)=f(0)+(増減)です。
入力例3に対して目に見えるようにしました→https://poyo-poyo.github.io/ARC082F_in/
あまり良い例ではなかったかも。(t, a)=(231, 55)で何か感じとってください。
解答例
おわりに
gistbox無くなるんですか……。
