No.3582 部分和不等式
p-adic問題文
最初に $2$ 個の正整数 $N, Q$ が与えられます。
集合 $X$ が最初は空集合として与えられています。
以下に説明する $Q$ 個のクエリを与えられた順に処理することで $X$ を更新していき、全てのクエリを処理し終えた時点で条件「全ての $N$ 次元整数ベクトルが $X$ に属す」が成り立つか否かを判定してください。
各クエリは、$2$ 個の $N$ 以下の非負整数 $A, B$ と整数 $M$ と、$N$ 以下の正整数のみからなる要素数 $A$ の集合 $S$ と $N$ 以下の正整数のみからなる要素数 $B$ の集合 $T$ の組 $(A,B,M,S,T)$ です。
クエリ $(A,B,M,S,T)$ を処理するには、条件 $\sum_{i \in S} x_i \leq M + \sum_{j \in T} x_j$ を満たす全ての $N$ 次元の整数ベクトル $x$ を $X$ に挿入することで $X$ を更新してください。
ただし $N$ 次元の整数ベクトル $x$ と $N$ 以下の正整数 $i$ に対し、$x_i$ で $x$ の $i$ 個目の成分を表します。
入力
入力は以下の形式で標準入力から $3Q+1$ 行で与えられます：
- $1$ 行目に $N,Q$ が半角空白区切りで与えられます。
- $Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリが $3q - 1$ 行目から $3q + 1$ 行目までに $3$ 行で与えられます。
$N$ $Q$ ($1$ 個目のクエリ) $\vdots$ ($Q$ 個目のクエリ)
各クエリ $(A,B,M,S,T)$ は以下の形式で $3$ 行で与えられます：
- $1$ 行目に $A,B,M$ が半角空白区切りで与えられます。
- $2$ 行目に
Sという文字と $S$ の各要素が昇順に半角空白区切りで与えられます。 - $3$ 行目に
Tという文字と $T$ の各要素が昇順に半角空白区切りで与えられます。
$A$ $B$ $M$ S $S$ T $T$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^3$ を満たす整数
- $Q$ は $1 \leq Q \leq 10^3$ を満たす整数
- $Q$ 以下の任意の正整数 $q$ に対し、$q$ 個目のクエリ $(A,B,M,S,T)$ は 以下を満たす：
- $A$ は $0 \leq A \leq N$ を満たす整数
- $B$ は $0 \leq B \leq N$ を満たす整数
- $M$ は $- 10^{9} \leq M \leq 10^{9}$ を満たす整数
- $S$ は $N$ 以下の正整数のみからなる要素数 $A$ の集合
- $T$ は $N$ 以下の正整数のみからなる要素数 $B$ の集合
- $N$ 以下の任意の正整数 $i$ に対し、以下の $2$ 数の和は $2$ 以下：
- クエリ $(A,B,M,S,T)$ のうち $i \in S$ を満たすものの個数
- クエリ $(A,B,M,S,T)$ のうち $i \in T$ を満たすものの個数
出力
全てのクエリを処理し終えた時点で条件「全ての $N$ 次元整数ベクトルが $X$ に属す」が成り立つ場合はYesと、そうでない場合はNoと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 1 0 1 S 1 T
出力
No
$1$ 個目のクエリ $(1,0,1,\{1\},\{0\})$ により、$X$ は空集合 $\{\}$ から
$\displaystyle \{\} \cup \left\{x \in \mathbb{Z}^1 \middle| \sum_{i \in \{1\}} x_i \leq 1 + \sum_{j \in \{\}} x_j \right\} = \{x \in \mathbb{Z}^1 \mid x_1 \leq 1\}$
に置き換わります。例えば $N = 1$ 次元整数ベクトル $(2)$ が $X$ に属しません。
サンプル2
入力
1 2 1 0 0 S 1 T 0 1 1 S T 1
出力
Yes
$1$ 個目のクエリ $(1,0,0,\{1\},\{0\})$ により、$X$ は空集合 $\{\}$ から
$\displaystyle \{\} \cup \left\{x \in \mathbb{Z}^1 \middle| \sum_{i \in \{1\}} x_i \leq 0 + \sum_{j \in \{\}} x_j \right\} = \{x \in \mathbb{Z}^1 \mid x_1 \leq 0\} $
に置き換わります。更に $2$ 個目のクエリ $(0,1,1,\{\},\{1\})$ により、$X$ は
$\displaystyle \{x \in \mathbb{Z}^1 \mid x_1 \leq 0\} \cup \left\{x \in \mathbb{Z}^1 \middle| \sum_{i \in \{\}}^{1} x_i \leq 1 + \sum_{j \in \{1\}} x_j \right\} = \{x \in \mathbb{Z}^1 \mid x_1 \leq 0 \lor 0 \leq 1 + x_1\} = \mathbb{Z}^1 $
に置き換わります。特に全ての $N = 1$ 次元整数ベクトルが $X$ に属します。
サンプル3
入力
2 2 0 2 2 S T 1 2 2 0 -1 S 1 2 T
出力
Yes
$1$ 個目のクエリ $(0,2,2,\{\},\{1,2\})$ により、$X$ は空集合 $\{\}$ から
$\displaystyle \{\} \cup \left\{x \in \mathbb{Z}^2 \middle| \sum_{i \in \{\}} x_i \leq 2 + \sum_{j \in \{1,2\}} x_j \right\} = \{x \in \mathbb{Z}^2 \mid 0 \leq 2 + x_1 + x_2\} $
に置き換わります。更に $2$ 個目のクエリ $(2,0,-1,\{1,2\},\{\})$ により、$X$ は
$\displaystyle \{x \in \mathbb{Z}^2 \mid 0 \leq 2 + x_1 + x_2\} \cup \left\{x \in \mathbb{Z}^2 \middle| \sum_{i \in \{1,2\}} x_i \leq -1 + \sum_{j \in \{\}} x_j \right\} = \{x \in \mathbb{Z}^2 \mid 0 \leq 2 + x_1 + x_2 \lor x_1 + x_2 \leq -1\} = \mathbb{Z}^2 $
に置き換わります。特に全ての $N = 2$ 次元整数ベクトルが $X$ に属します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。