No.3472 ジャッジキューの待ち時間クエリ
yuki2006問題文
あるオンラインジャッジにはジャッジサーバーが 1 台あり、$N$ 個の提出をキューの先頭から順番に処理します。提出 $i$ の実行時間は $T_i$ ミリ秒です。すべての提出は時刻 $0$ にキューに入っており、サーバーは時刻 $0$ から処理を開始します。
提出 $i$ のジャッジが完了する時刻は $C_i = T_1 + T_2 + \cdots + T_i$ です。
$Q$ 個のクエリが与えられます。各クエリでは時刻 $X_j$ が与えられるので、時刻 $X_j$ までにジャッジが完了した提出の数を答えてください。つまり $C_i \le X_j$ を満たす $i$ の個数を求めてください。
入力
$N\ Q$ $T_1\ T_2\ \ldots\ T_N$ $X_1$ $X_2$ $\vdots$ $X_Q$
制約はすべて整数
- $1 \le N \le 200{,}000$
- $1 \le Q \le 200{,}000$
- $1 \le T_i \le 10^9$
- $0 \le X_j \le 10^{18}$
出力
$Q$ 行に、各クエリの答えを出力してください。 最後に改行してください。
部分点
この問題にはサブタスクによる部分点が設定されています。
| サブタスク名 | 配点 | 制約 |
|---|---|---|
| サンプル | 10 点 | サンプルケース |
| Small | 30 点 | N, Q ≤ 200 |
| Large | 60 点 | N, Q ≤ 200,000 |
サンプル
サンプル1
入力
5 3 3 1 4 1 5 5 14 2
出力
2 5 0
各提出の完了時刻は $C = [3, 4, 8, 9, 14]$ です。
$X = 5$: $C_1 = 3 \le 5$, $C_2 = 4 \le 5$, $C_3 = 8 > 5$ → 2 個
$X = 14$: すべて $C_i \le 14$ → 5 個
$X = 2$: $C_1 = 3 > 2$ → 0 個
サンプル2
入力
3 4 10 10 10 0 9 10 30
出力
0 0 1 3
完了時刻は $C = [10, 20, 30]$ です。
$X = 0$: 0 個、$X = 9$: 0 個、$X = 10$: 1 個、$X = 30$: 3 個
サンプル3
入力
1 1 1000000000 1000000000
出力
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。