0-indexedで考えます。

倒産するならば、\(2^{61}\)日経過するより前に倒産します。

\[ D_{i} = \begin{cases} A_{i} - B_{i} - C_{i}\ (0\le i\lt N) \\ D_{i-N}\ (\text{otherwise}) \end{cases} \]

と長さ \(2^{61}\) の数列 \(D\) を定義すると、クエリ\((L,S)\)の答えは、 \(S + D_{L}+D_{L+1}+\cdots+D_{R}\lt 0\)を満たす最小の\(R(L\le R)\)を発見せよ。(存在しない場合は0を出力せよ)という問題が解ければよいでしょう。

\(0\le i\le 60, 0\le j \lt N\)を満たす整数組\((i,j)\)すべてに対して、以下の三つの情報を前計算した上で二分探索すると解けます。(俗にダブリングと呼ばれることをしています。)

• \(X_{i,j} := \sum_{k=0}^{2^i-1} D_{j+k}\)
• \(Y_{i,j} := \min_{k=0}^{2^i-1} \sum_{p=0}^{k} D_{j+p}\)
  • 言葉でいうと、\(D\)の\(j\)番目の要素を左端とした長さ\(2^i\)以下の連続分列に渡る、総和の最小値
• \(Z_{i,j} = (j+2^{i})\pmod{N}\)

\(i=0,1,2,\dots,60\)の順で計算することを考えると、\(X_{i},Y_{i},Z_{i}\)の計算が一つの\(i\)について\(O(N)\)でできることがわかります。

一番非自明な点は\(Y_{i}\)の計算だと思いますが、 \(Y_{i,j} = \min\{Y_{i-1,j},X_{i-1,j}+Y_{i-1,Z_{i-1,j}}\}\) に注意するとできます。

倒産しないケースは\(2^{61}-1\)進んで倒産していなかったら0を出力するで良いと思いますが、64bitで扱えない大きさの整数が計算途中に出現しそうです。C++で実装する場合、倒産するかどうかの判定は公式解説と同じ方法で処理するのが楽だと思います(\(N\)ステップ進んで一度も倒産せず資金が初期金額から増えたら倒産しない)