問題一覧 > 通常問題

No.2169 To Arithmetic

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : first_vilfirst_vil / テスター : hamamuhamamu milkcoffeemilkcoffee
2 ProblemId : 8414 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-18 16:02:18

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。あなたは $A$ に対して以下の操作を $0$ 回以上の好きな回数行うことができます。

  • 整数組 $(l,r)\ (1 \le l \le r \le N)$ を選び、各 $i\ (l \le i \le r)$ について $A_i:=A_i+1$ とする。

各 $i\ (1 \le i \le Q)$ について、$A$ を公差が $d_i$ である等差数列にするまでの操作回数の最小値を求めてください。

入力

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$d_1$
$d_2$
$\vdots$
$d_Q$
  • 入力はすべて整数
  • $2 \le N \le 2 \times 10^5$
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le A_i \le 10^9$
  • $|d_i| \le 10^9$

出力

$Q$ 行出力してください。

$i\ (1 \le i \le Q)$ 行目には、$A$ を公差が $d_i$ である等差数列にするまでの操作回数の最小値を出力し、最後に改行してください。

サンプル

サンプル1
入力
4 3
1 4 6 5
2
0
-1
出力
4
6
7

$d_1=2$ については以下のような操作列が操作回数を最小化します。

  • $(l,r)=(1,1)$ とした操作を $1$ 回行う。$A=(2,4,6,5)$ となる。
  • $(l,r)=(4,4)$ とした操作を $3$ 回行う。$A=(2,4,6,8)$ となる。

$d_2=0$ については以下のような操作列が操作回数を最小化します。

  • $(l,r)=(1,1)$ とした操作を $3$ 回行う。$A=(4,4,6,5)$ となる。
  • $(l,r)=(1,2)$ とした操作を $2$ 回行う。$A=(6,6,6,5)$ となる。
  • $(l,r)=(4,4)$ とした操作を $1$ 回行う。$A=(6,6,6,6)$ となる。

$d_3=-1$ については以下のような操作列が操作回数を最小化します。

  • $(l,r)=(1,1)$ とした操作を $4$ 回行う。$A=(5,4,6,5)$ となる。
  • $(l,r)=(1,2)$ とした操作を $3$ 回行う。$A=(8,7,6,5)$ となる。
サンプル2
入力
3 2
3 6 9
3
-3
出力
0
12
サンプル3
入力
15 8
5 4 5 19 7 7 6 28 19 6 6 9 12 10 25
-6
6
-19
-28
36
13
19
-10
出力
120
97
286
412
484
174
249
165

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。