ステップ 1 : 動的計画法の利用

$dp[i] : i$ 番目のテレポーターのある階に移動するのにかかる最小の時間
という動的計画法を考えます。

テレポーター $1$ のある階に移動するための最短経路は、$1$ 階から階段を使って移動するしかありません。

また、今回の問題では、ビルの $1$ 階から移動することから、$1 \leq i \leq M - 1$ についてそれぞれ、$dp[i] < dp[i + 1]$ が成り立ちます。

よって、テレポーター $i \: (2 \leq i \leq M)$ のある階に移動する階に移動するための最短経路は、

• テレポーター $j \: (1 \leq j \leq i - 1)$ のある階からテレポートする。
• テレポーター $j$ のある階から階段を使って移動する。

のいずれかなので、

$dp[1] = (A_1 - 1) \times T$ として、
$dp[i] = \min(dp[j] + (A_i - A_j)^2 + C, dp[j] + (A_i - A_j) \times T)$

と遷移をすることができます。

ステップ 2 : 動的計画法の高速化 (Convex Hull Trickの利用)

ステップ $1$ の動的計画法を愚直に遷移して行うと、$O(M^2)$ の時間がかかり実行時間制限に間に合いません。

テレポーター $j$ のある階からテレポーター $i$ のある階にテレポーターを通って移動するためには、 $(A_i - A_j)^2 + C$ の時間がかかりますが、
この式を展開すると、$A_i^2 - 2 A_i A_j + A_j^2 + C$ となります。

この式において、$A_i^2 + C$ は独立して計算できるため、$-2 A_i A_j + A_j^2$ が問題になりますが、傾き $-2 A_j$、切片 $A_j^2$ の $A_i$ についての一次関数とみなすことができます。

よって、傾き $- 2 A_j$、切片 $A_j^2 + dp[j]$ の直線群における、$x = A_i$ のときの最小の値を求めればよいです。
これは、Convex Hull Trick を用いると高速に求めることができます。

$x = A_i$ のときの最小の値を $k$ とすると、

$dp[1] = (A_1 - 1) \times T$ として、
$dp[i] = \min(A_i^2 + C + k, dp[i - 1] + (A_i - A_{i - 1}) \times T)$

と遷移することができ、全体で $O(M)$ の時間で動的計画法を行うことができます。

ステップ 3 : クエリを処理する

今回の問題におけるクエリである、$X_i$ 階に移動するのにかかる最小の時間を求めましょう。

ステップ $1$ とステップ $2$ から、各テレポーターのある階へ移動するのにかかる最小の時間が分かっているため、

• $X_i$ 階以下の階にある最大のテレポーターのある階 (存在しない場合は $1$ 階)
• $X_i$ 階より上の階にある最小のテレポーターのある階 (存在しない場合は考慮しない)

のいずれかから階段を使って移動することが最適となります。

よって、それぞれの階について、$1$ 階から移動する時間を前計算しておくことができます。

結果として、$O(N + M + Q)$ でこの問題を解くことができました。