区画 \((X, Y)\) を中心として、高さ \(h\) のピラミッドを立てる時の、区画 \((x, y)\) につまれる石の個数を \(Num(X, Y, h, x, y)\) と定義します。
問題文から、

\[ Num(X, Y, h, x, y) = \max(0, h - \max(|X - x|, |Y - y|)) \]

です。
ここで、max 関数の2項目について、\(y\) を固定し、\(d = |Y - y|\) とすると、
\(x < X - d\) の時 \(h - (X - x)\)
\(X - d \leq x \leq X + d\) の時 \(h - d\)
\(X + d < x\) の時 \(h - (x - X)\)
となります。
上の3つの関数をそれぞれ \(N_1(X, Y, h, x), N_2(X, Y, h, x), N_3(X, Y, h, x)\) とし、それぞれ上で定義された区間外では \(0\) の値を取るとすると、最終的に区画 \((x, y)\) につまれる石の個数は

\[ \max_{1 \leq i \leq N} Num(X_i, Y_i, h_i, x, y) = \max_{1\leq i\leq N} \max_{p = 1, 2, 3}(N_p(X_i, Y_i, h_i, x, y))\\ = \max_{p = 1, 2, 3}(\max_{1 \leq i \leq N}(N_p(X_i, Y_i, h_i, x, y)) \]

よって、\(N_1, N_2, N_3\) それぞれで最大値を求めた後、3関数の最大値を各x について求めれば良いです。

\(N_1\) について、関数は \(x + a_i\;\; (x < b_i)\) の形で一般化されます。
よって、各要素が\(0\)に初期化された配列 \(A\) を用意して 、 \(A_{b_i} = a_i\) と前処理をした後、 \(x = W-1,\ldots, 1\) について \(A_{x-1} = max(A_{x-1}, A_x - 1)\) と処理することで、計算できます。
\(N_3\) についても同様に計算できます。

\(N_2\) について、これはセグメント木やpriority_queueを用いるなどして高速に計算できます。

\(N_1, N_3\) を求める計算量が \(O(N + W)\), \(N_2\) を求める計算量が \(O(W + N\log N)\) や \(O((W + N)\log W)\) となり、全体で \(O(H(W + N\log N))\) などで計算できました。

実装例

座標系を \(u = x + y, v = x - y\) にすると、つまれる個数に \(x + a, -x + a\) の形のみが出てくるようになり、\(O((H + W)(H + W + N))\) で計算することもできます。