2010JOI本選1 旅人 解説

問題リンク

解説

愚直にシミュレーションすることを考えると、時間計算量は になって、間に合いません。

毎日の移動で、区間の和をひとつずつ足して計算するのは無駄なので、累積和を使って高速化すると、計算量を にすることができます。

また、毎日の移動で、それぞれの区間を何度通ったかを imos 法などで高速に記録し、最後にまとめて処理しても良いです。