問題一覧 > 通常問題

No.2643 Many Range Sums Problems

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : KoiKoi / テスター : shobonvipshobonvip noya2noya2
3 ProblemId : 10660 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-19 00:46:49

問題文

各 $i=1,2,\ldots ,N$ について以下の独立な問題を解いてください。

以下の条件を全て満たす整数列 $A=(A_1,A_2,\ldots ,A_N)$ が存在するか判定してください。

  • 全ての $j=1,2,\ldots ,N$ について $0\le A_j\le K$
  • 全ての $j=1,2,\ldots ,N$ について $\displaystyle j\neq i\Rightarrow \sum_{k=j}^{R_j} A_k=X_j$
    • ここで $j\le R_j$ が保証されます。

制約

  • $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$)
  • 入力は全て整数

入力

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

出力

$N$ 行出力してください。 $k$ 行目には $i=k$ のとき条件を満たす整数列 $A$ が存在する場合は Yes を、存在しない場合は No を出力してください。

サンプル

サンプル1
入力
3 2
2 1
2 2
3 0
出力
Yes
Yes
No

$i=2$ について、例えば $A=(1,0,0)$ は $0\leq A_1\leq 2,\ 0\leq A_2\leq 2,\ 0\leq A_3\leq 2$ で、 $A_1+A_2=1,\ A_3=0$ なので全ての条件を満たしています。

$i=3$ について、全ての条件を満たす $A$ は存在しません。

サンプル2
入力
5 0
5 0
5 0
5 0
5 0
5 0
出力
Yes
Yes
Yes
Yes
Yes

サンプル3
入力
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
出力
No
No
No
Yes
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No

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