問題一覧 > 通常問題

No.2643 Many Range Sums Problems

レベル : / AI推定難易度 : 1975 / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 23
作問者 : Koi / テスター : shobonvip noya2
お気に入りにしたユーザー ProblemId : 10660 / 自分の提出
問題文最終更新日: 2024-02-19 00:46:49
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. Back to the original
traP 作問ハッカソンコンテスト 002(day2) (順位表) の他の問題:

Problem Statement

For each $i=1,2,\ldots ,N$, solve the following independent problem.

Determine whether there exists an integer sequence $A=(A_1,A_2,\ldots ,A_N)$ satisfying all of the following conditions.

  • $0\le A_j\le K$ for all $j=1,2,\ldots ,N$
  • $\displaystyle j\neq i\Rightarrow \sum_{k=j}^{R_j} A_k=X_j$ for all $j=1,2,\ldots ,N$
    • Here, $j\le R_j$ is guaranteed.

Constraints

  • $1\leq N\leq 5000$
  • $0\leq K\leq 10^9$
  • $i\leq R_i\leq N$ ($1\leq i\leq N$)
  • $0\leq X_i\leq NK$ ($1\leq i\leq N$)
  • All input values are integers.

Input

$N\ K$
$R_1\ X_1$
$R_2\ X_2$
$\vdots$
$R_N\ X_N$

Output

Print $N$ lines. On the $k$-th line, print Yes if there exists an integer sequence $A$ satisfying the conditions for $i=k$, and No otherwise.

Sample

Sample 1
Input
3 2
2 1
2 2
3 0
Output
Yes
Yes
No

For $i=2$, for example, $A=(1,0,0)$ satisfies $0\leq A_1\leq 2,\ 0\leq A_2\leq 2,\ 0\leq A_3\leq 2$ and $A_1+A_2=1,\ A_3=0$, so all the conditions are satisfied.

For $i=3$, no $A$ satisfies all the conditions.

Sample 2
Input
5 0
5 0
5 0
5 0
5 0
5 0
Output
Yes
Yes
Yes
Yes
Yes

Sample 3
Input
20 10000
1 9999
8 69967
16 139927
12 89951
10 59967
20 149915
20 139925
20 129928
15 69958
12 29973
12 19983
14 29983
20 79962
15 19990
16 19989
16 9996
17 9998
18 9991
19 9999
20 9993
Output
No
No
No
Yes
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No

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