問題一覧 > 通常問題

No.1093 区間の和 / Sum of Range

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 51
作問者 : nullnull / テスター : butsurizukibutsurizuki
0 ProblemId : 4568 / 出題時の順位表
問題文最終更新日: 2020-06-24 02:24:47

問題文

数列 $a_1, a_2, \dots, a_N$ があります。
$\displaystyle S_i = \sum_{j = i}^{i + K - 1} a_j = a_i + a_{i+1} + \dots + a_{i + K - 1}$ とし、多重(追記)集合 $S = \{S_1, S_2, \dots, S_{N-K + 1}\}$ とします。
この時、$l(1 \le l \le Q)$ 番目のクエリでは $x_l$ 以下である $S$ の要素の個数を出力してください。
言い換えると、$S_1, S_2, \dots, S_{N - K + 1}$ のうち $x_l$ 以下であるものの個数を出力してください。

入力

$N\ K$
$a_1\ a_2\ \dots\ a_N$
$Q$
$x_1$
$x_2$
$\dots$
$x_Q$

$1 \le N, Q \le 10^5$
$-10^4 \le a_i \le 10^4$
$1 \le K \le N$
$-10^9 \le x_l \le 10^9$
入力はすべて整数。

出力

改行区切りで $Q$ 行にわたって答えを出力せよ。最後に改行せよ。

サンプル

サンプル1
入力
10 2
1 2 3 4 5 6 7 8 9 10
10
19
18
17
15
13
11
9
7
5
3
出力
9
8
8
7
6
5
4
3
2
1

$S=\{3,5,7,9,11,13,15,17,19\}$ です。

出典

YSF Beginner Contest: F - 区間の和 / Sum of Range
writer: null
tester: butsuri_0523
HackerRank の規約に基づいて移植されました。一部サイトの都合などで改変したところがあります。

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