問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : e869120e869120 / テスター : hirakich1000000007hirakich1000000007
2 ProblemId : 3321 / 出題時の順位表
問題文最終更新日: 2020-07-03 00:53:54

問題文

$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$ にする事が出来ます。

制約

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

  • $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

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