/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
F 問題と F2 問題は同じ問題ですが、M の制約が異なります。F2 問題では M = 5 です。
正整数 M が与えられます。ここで、以下の問題を考えます。
Bucket正整数 N と長さ N の非負整数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) が与えられます。A,B の要素は全て 0 以上 M 以下です。
1 から N の番号が付いた N 個のバケツがあります。全てのバケツには水が M L まで入ります。始め、バケツ i には A_i L の水が入っています。
あなたは以下の操作を好きな回数行うことが出来ます。
- 異なる 2 個のバケツ i,j を選ぶ。以下の条件を両方満たしている間、バケツ i からバケツ j に水を移し続ける。
- バケツ i にまだ水が残っている。
- バケツ j に入っている水の量が M L 未満である。
あなたの目標は、全ての i についてバケツ i に水が B_i L 入っている状況にすることです。目標を達成することが出来るか判定してください。
M+1 行 M+1 列の非負整数行列 X=(X_{i,j})(0 \le i,j \le M) が与えられます。以下のクエリを Q 回処理してください。
- 0 \le i,j \le M を満たす非負整数 i,j,Y が与えられる。X_{i,j} を Y に変更する。その後、以下の手順で非負整数列 A,B を得る。
- 非負整数列 A,B を空数列で初期化する。
- 以下を i = 0,1,\dots,M の順に行う。
- 以下を j = 0,1,\dots,M の順に行う。
- A の末尾に i を、B の末尾に j を追加する操作を X_{i,j} 回行う。
- 長さ N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} の非負整数列 A,B について Bucket を解いたときの答えを求めよ。
制約
- M = 5
- 1 \le Q \le 10^6
- 0 \le X_{i,j},Y \le 10^{17}
- 0 \le i,j \le M
- 全ての時点で \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} \ge 1
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
M Q
X_{0,0}\ X_{0,1}\ \dots\ X_{0,M}
X_{1,0}\ X_{1,1}\ \dots\ X_{1,M}
\vdots
X_{M,0}\ X_{M,1}\ \dots\ X_{M,M}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下の形式で与えられる。
i\ j\ Y
出力
Q 行出力せよ。i 行目には \mathrm{query}_i において、目標を達成することが出来るならば Yes を、出来ないならば No を出力せよ。
入力例 1
5 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 4 0 1 1 5 1
出力例 1
Yes No Yes
それぞれのクエリ時点で得られる A,B は以下の通りです。
- 1 番目のクエリを処理する時点では、A=(0,3,3),B=(0,1,5)
- 2 番目のクエリを処理する時点では、A=(0,3,3,4),B=(0,1,5,0)
- 3 番目のクエリを処理する時点では、A=(0,1,3,3,4),B=(0,5,1,5,0)
入力例 2
5 10 61717749303507807 83849626163233111 84388501405824055 8514730661576685 8408052512772637 42085112989954358 33333333333333333 70477132070314067 43546706335438313 61370380435458585 99101823689638606 77669930608921552 33333333333333333 21459633523757247 8151410984806542 14183403125185219 68299186110683565 35549692732468863 98146856836553017 53630682913685434 12400422817799555 29967281381593348 67521547136428867 48353536740933612 97356055491517734 55777507072845580 59235925940735000 6228770338558507 41778108608223669 60544364859700647 5960356361755846 59147828067221624 65687376011190687 33333333333333333 31563848832259443 98724011871535047 2 3 1333175914347793 3 4 80371774347266293 2 1 20920094361040152 2 3 793636751630698 0 5 68209364995103050 2 0 98643963346205063 3 2 7931291059115265 0 1 79380494404548821 2 5 6440038070576840 2 3 88122600737306767
出力例 2
No No No No No Yes No Yes No Yes
Score : 300 points
Problem Statement
Problems F and F2 are the same problem with different constraints on M. In Problem F2, M = 5.
You are given a positive integer M. Consider the following problem.
BucketYou are given a positive integer N and non-negative integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N) of length N. All elements of A and B are between 0 and M, inclusive.
There are N buckets numbered 1 to N. Each bucket can hold up to M liters of water. Initially, bucket i contains A_i liters of water.
You may perform the following operation any number of times.
- Choose two distinct buckets i and j. Continue pouring water from bucket i into bucket j as long as both of the following conditions are satisfied:
- Bucket i still has water remaining.
- The amount of water in bucket j is less than M liters.
Your goal is to have exactly B_i liters of water in bucket i for all i. Determine whether the goal can be achieved.
You are given a non-negative integer matrix X=(X_{i,j})(0 \le i,j \le M) of (M+1) rows and (M+1) columns. Process the following queries Q times.
- You are given non-negative integers i,j,Y with 0 \le i,j \le M. Change X_{i,j} to Y. Then, obtain non-negative integer sequences A and B by the following procedure.
- Initialize non-negative integer sequences A and B as empty sequences.
- For i = 0,1,\dots,M in this order:
- For j = 0,1,\dots,M in this order:
- Do this X_{i,j} times: append i to the end of A and j to the end of B.
- Solve Bucket for the non-negative integer sequences A and B of length N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}.
Constraints
- M = 5
- 1 \le Q \le 10^6
- 0 \le X_{i,j},Y \le 10^{17}
- 0 \le i,j \le M
- \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} \ge 1 at any time.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
M Q
X_{0,0}\ X_{0,1}\ \dots\ X_{0,M}
X_{1,0}\ X_{1,1}\ \dots\ X_{1,M}
\vdots
X_{M,0}\ X_{M,1}\ \dots\ X_{M,M}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in the following format:
i\ j\ Y
Output
Output Q lines. The i-th line should contain Yes if the goal can be achieved in \mathrm{query}_i, and No otherwise.
Sample Input 1
5 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 4 0 1 1 5 1
Sample Output 1
Yes No Yes
The sequences A and B obtained at each query are as follows:
- At the time of processing the first query: A=(0,3,3),B=(0,1,5)
- At the time of processing the second query: A=(0,3,3,4),B=(0,1,5,0)
- At the time of processing the third query: A=(0,1,3,3,4),B=(0,5,1,5,0)
Sample Input 2
5 10 61717749303507807 83849626163233111 84388501405824055 8514730661576685 8408052512772637 42085112989954358 33333333333333333 70477132070314067 43546706335438313 61370380435458585 99101823689638606 77669930608921552 33333333333333333 21459633523757247 8151410984806542 14183403125185219 68299186110683565 35549692732468863 98146856836553017 53630682913685434 12400422817799555 29967281381593348 67521547136428867 48353536740933612 97356055491517734 55777507072845580 59235925940735000 6228770338558507 41778108608223669 60544364859700647 5960356361755846 59147828067221624 65687376011190687 33333333333333333 31563848832259443 98724011871535047 2 3 1333175914347793 3 4 80371774347266293 2 1 20920094361040152 2 3 793636751630698 0 5 68209364995103050 2 0 98643963346205063 3 2 7931291059115265 0 1 79380494404548821 2 5 6440038070576840 2 3 88122600737306767
Sample Output 2
No No No No No Yes No Yes No Yes