各クエリで以下のような処理を実装することでクエリあたり\(\mathrm{O}(N)\)で解くことが可能です。(証明は公式解説の小課題1にあります。)

ans,rem = 0,0
for a in A:
  rem = max(0,rem+a)
  ans += rem//K
  rem = rem%K

ここで、以下のように変形します。\(\mathrm{rem}\)が常に\(0\)以上\(2K\)未満となることから、\(\mathrm{rem}\)から\(K\)減算する操作が高々一回に抑えられます。

ans,rem = 0,0
for a in A:
  if a>0:
    rem += a%K
    ans += a//K
    if rem>=K:
      rem -= K
      ans += 1
  else:
    rem = max(0,rem+a)

\(S\)を\(\mathrm{rem}\)をキーとして\(\mathrm{ans}\)を持つ平衡二分探索木とします。各クエリについて適切なタイミングで\(S\)にそのクエリに対応するノードを挿入することで、以下のようなコードで上の処理を実現できます。

for a in A:
  if a>0:
    S.rem += a%K
    S.ans += a//K
    l,r = S.split(K)
    r.rem -= K
    r.ans += 1
    S = merge(r,l)
  else:
    S.rem += a
    l,r = S.split(0)
    l.rem = 0
    S = merge(l,r)

splitは\([(\)引数未満の\(\mathrm{rem}\)からなる平衡二分探索木\(),(\)引数以上の\(\mathrm{rem}\)からなる平衡二分探索木\()]\)を返す関数です。
\(K\)以上のものをsplitし、\(-K\)してmergeする操作の際に\(\mathrm{rem}\)の順序が壊れそうに見えますが、\(\mathrm{rem}\)として有り得る最大値が\(K-1+a \% K\)、最小値が\(a \% K\)であることから順序が保たれます。
よってmerge/split、\(\mathrm{rem}\),\(\mathrm{ans}\)への加算、\(\mathrm{rem}\)の\(0\)への更新が可能な平衡二分探索木を用いて解くことができます。
同じ左端を持つクエリのノードをまとめることで、計算量は\(\mathrm{O}((N + Q) \log \mathrm{min}(N, Q))\)となります。
RBSTを用いた実装例 (C++, 737ms)