No.2643 Many Range Sums Problems
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Koi
noya2