問題一覧 > 通常問題

No.1245 ANDORゲーム(calc)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 140
作問者 : 👑 tute7627tute7627 / テスター : tempura_pptempura_pp
9 ProblemId : 4335 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-10-02 18:41:17

問題文

あなたは以下のようなゲームを行うことにしました。

  • ゲームの開始時にあなたは非負整数 $T$ を持っており、スコアは $0$ である。
  • 長さ $N$ の数列 $A$ を用いて以下の操作を $N$ 回繰り返す。
    • $i$ 回目の操作では、現在持っている整数を $X$ として、$X$ を以下のどちらかに変化させる。
      • $X$ と $A_i$ の bitwise and
      • $X$ と $A_i$ の bitwise or
    • 各操作後に、スコアが $|(変化後のX) - (変化前のX)|$ 増加する。
あなたはある操作手順 $S$ について、以下のクエリを $Q$ 個処理することにしました。
  • $i$ 番目のクエリでは、初期値 $T = t_i$ であり、操作手順 $S$ に従って操作を行った時の $N$ 回の操作後のスコアを求める。
それぞれのクエリの答えを求めてください。

入力

$N \ Q$
$A_1 \ A_2 \dots A_N$
$S$
$t_1 \ t_2 \dots t_Q$

  • $1 \le N,Q \le 10^5$
  • $0 \le A_i \le 10^9$
  • $S$ は0と1からなる長さ $N$ の文字列である。
  • $S$ の $i$ 文字目が0である場合、$i$ 回目の操作で bitwise and を選択する。
    $S$ の $i$ 文字目が1である場合、$i$ 回目の操作で bitwise or を選択する。
  • $0 \le t_i \le 10^9$

出力

$i$ 行目には $i$ 番目のクエリの答えを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2 2
2 1
01
1 2
出力
2
1

bitwise and, bitwise or の順で選択します。
・初期値が $1$ の場合
$1$ 回目の操作では、持っている整数は $1 \to 0$ となり、スコアは $1$ になります。
$2$ 回目の操作では、持っている整数は $0 \to 1$ となり、スコアは $2$ になります。
・初期値が $2$ の場合
$1$ 回目の操作では、持っている整数は $2 \to 2$ となり、スコアは $0$ のままです。
$2$ 回目の操作では、持っている整数は $2 \to 3$ となり、スコアは $1$ になります。

サンプル2
入力
4 3
0 0 0 0
1111
1 2 3
出力
0
0
0

初期値がどの値でも結果は同じです。

サンプル3
入力
6 7
8 24 31 25 8 25
010100
18 28 9 5 31 0 21
出力
60
54
35
47
57
42
63

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