問題一覧 > 通常問題

No.3472 Judge Queue Waiting Time Queries

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 50
作問者 : yuki2006
お気に入りにしたユーザー ProblemId : 4253 / 自分の提出
問題文最終更新日: 2026-03-10 02:46:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder 2026新ジャッジ contest (順位表) の他の問題:

Problem Statement

An online judge has 1 judge server, which processes $N$ submissions in order from the front of the queue. The execution time of submission $i$ is $T_i$ milliseconds. All submissions are in the queue at time $0$, and the server starts processing at time $0$.

The time at which the judging of submission $i$ completes is $C_i = T_1 + T_2 + \cdots + T_i$.

You are given $Q$ queries. Each query gives a time $X_j$; answer the number of submissions whose judging has completed by time $X_j$. In other words, find the number of $i$ satisfying $C_i \le X_j$.

Input

$N\ Q$
$T_1\ T_2\ \ldots\ T_N$
$X_1$
$X_2$
$\vdots$
$X_Q$

All constraints are integers.

  • $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}$

Partial Score

This problem has partial scoring based on subtasks.

SubtaskScoreConstraints
サンプル10% (25 pts)サンプルケース
Small30% (75 pts)N, Q ≤ 200
Large60% (150 pts)追加制約なし

Output

Output the answer to each query over $Q$ lines. Print a newline at the end.

Sample

Sample 1
Input
5 3
3 1 4 1 5
5
14
2
Output
2
5
0

The completion times of the submissions are $C = [3, 4, 8, 9, 14]$.
$X = 5$: $C_1 = 3 \le 5$, $C_2 = 4 \le 5$, $C_3 = 8 > 5$ → 2 submissions
$X = 14$: all $C_i \le 14$ → 5 submissions
$X = 2$: $C_1 = 3 > 2$ → 0 submissions

Sample 2
Input
3 4
10 10 10
0
9
10
30
Output
0
0
1
3

The completion times are $C = [10, 20, 30]$.
$X = 0$: 0 submissions, $X = 9$: 0 submissions, $X = 10$: 1 submission, $X = 30$: 3 submissions

Sample 3
Input
1 1
1000000000
1000000000
Output
1

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