No.868 ハイパー部分和問題

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 27
作問者 : e869120e869120 / テスター : hirakich1000000007hirakich1000000007
2 ProblemId : 3321 / 出題時の順位表

問題文

$N$ 個の自然数から成る数列 $A = [A_1, A_2, A_3, ..., A_N]$ が与えられます。また、整数 $K$ が与えられます。

さて、これについて $Q$ 回の操作を行います。

  • 数列の $x_i$ 番目の要素を $v_i$ に変更する。


各変更の後について、数列のいくつかの要素を選んで合計を $K$ にする事が出来るか求めてください。
ただし、数列の各要素は $1$ 回しか選べないものとします。
例えば、数列が $[4, 4, 9]$ の場合、合計が $0, 4, 8, 9, 13, 17$ となる合計 $6$ 通りの選び方があります。

制約

全ての入力データは以下の制約を満たします。

  • $N$ は $1$ 以上 $15 \ 000$ 以下の整数
  • $Q$ は $1$ 以上 $15 \ 000$ 以下の整数
  • $K$ は $1$ 以上 $15 \ 000$ 以下の整数
  • $A_i$ は $0$ 以上 $15 \ 000$ 以下の整数
  • $x_i$ は $1$ 以上 $N$ 以下の整数
  • $v_i$ は $0$ 以上 $15 \ 000$ 以下の整数

入力

$N$ $K$
$A_1$ $A_2$ $A_3$ ... $A_N$
$Q$
$x_1$ $v_1$
$x_2$ $v_2$
$x_3$ $v_3$
...
$x_Q$ $v_Q$

出力

$Q$ 行に渡って出力してください。
$i$ 行目には、$i$ 回目の操作が終わった後で部分和が $K$ となるようなものが存在する場合 $1$、そうでない場合 $0$ と出力してください。

サンプル

サンプル1
入力
3 8
4 4 9
3
1 4
2 5
3 3
出力
1
0
1

$1$ 回目の操作終了後の数列は $[4, 4, 9]$ です。$4 + 4 = 8$ という選び方が存在します。
$2$ 回目の操作終了後の数列は $[4, 5, 9]$ です。合計が $8$ となるような選び方は存在しません。
$3$ 回目の操作終了後の数列は $[4, 5, 3]$ です。$5 + 3 = 8$ という選び方が存在します。

サンプル2
入力
6 26
8 6 9 1 2 0
6
1 9
2 6
3 8
4 5
5 2
6 6
出力
1
1
1
0
0
1
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。