ABC188 D Snuke Prime
もし$ a_i, b_i \leq 10^5ぐらいならいもす法を用いて日ごとに利用するサービスの合計料金を求め, それと$ Cのうち小さいほうを答えに加算していけばよいが, 今回は$ a_i, b_i \leq 10^9なのでそれだと間に合わない.
考察すると, 加算する値に変化があるのはあるサービスの利用開始・利用終了時のみである. これは高々$ 2*10^5回しかないので順にシミュレートすることができる(それ以外の部分についてはまとめて計算することができる).