ARC082 F： Sandglass
Livedoorブログからの移動
はてなブログからの移動
解き方
- ある時刻におけるAの砂の量は、
max(E1+C, min(E2+C, a+C))の形で表せる（aは最初にAに入っている砂の量） - 各
r_iについて、E1,E2,Cを前計算しておき、クエリに対しては二分探索→最後だけ計算r_{i-1}のときの関数が求まれば、そこからr_iのときの前計算ができる
ハマったところ
r_iについて、二分探索→最後だけ計算の流れはそうだろうと思ったが、関数の形に対して思いつかなかった- 場合分けもっと増えると思って前計算諦めたんだけど、もう少し真面目に考えれば思いついたのだろうか。