\(N\) 日間愚直に積雪量を調べると計算量が \(O(N)\) となり、間に合いません。 そこで、\(N\) 日間をいくつかの区間に分け、その区間内でまとめて計算します。 具体的には、降雪のあった日から、次に降雪がある日の前日までを1つの区間とします。

\(D\) 日目の融雪後に積雪が \(S\) \([\mathrm{cm}]\) あり、次に降雪があるのが \(D'\) 日目である場合を考えます。
この時、\(d\) 日目 \((D\le d\lt D')\) の(融雪後の)積雪量は、\(\max(0,S-(d-D))\) \([\mathrm{cm}]\) です。
よって、この区間内で、地下鉄を利用する条件は \(S-(d-D)\ge K\) すなわち、\(S+D-K\ge d\) です。

以上より、\(D\) 日目以降、\(D'-1\) 日目以前で地下鉄を利用する日数は \(\max(0,\min(S+D-K,D'-1)-D+1)\) 日間です。

また、\(D'\) 日目の(融雪後の)積雪量は、\(D'\) 日目の降雪量を \(A\) \([\mathrm{cm}]\) として、\(\max(0,S-(D'-1-D))+A-1\) \([\mathrm{cm}]\) です。

上記の議論をまとめると、 \([1,a_1)\) 日の間の地下鉄利用日数を求める \(\rightarrow\) \(a_1\) 日目の積雪量を求める \(\rightarrow\) \([a_1,a_2)\) 日の間の地下鉄利用日数を求める \(\rightarrow\) \(a_2\) 日目の積雪量を求める \(\rightarrow\dots\rightarrow\) \([a_{M-1},a_{M})\) 日の間の地下鉄利用日数を求める \(\rightarrow\) \(a_M\) 日目の積雪量を求める \(\rightarrow\) \([a_M,N]\) 日の間の地下鉄利用日数を求める という流れで計算をすることができます。 計算量は \(O(M)\) です。