問題一覧 > 通常問題

No.206 数の積集合を求めるクエリ

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 172
作問者 : startcppstartcpp
10 ProblemId : 440 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:30

問題文

Warning : 想定解法の実行時間はC++で1秒弱($863$[ms])です。他の言語の場合、想定解法と同じ方法では通らない可能性があります。

長さ$L$の数列$A = {A[0], A[1], …, A[L-1]}$、長さ$M$の数列$B = {B[0], B[1], …, B[M-1]}$がある。
数列$A$, $B$はそれぞれ、重複する要素がない数列である。すなわち、
$0 \le i < j \le L-1$を満たす全ての$(i, j)$組について、$A[i] ≠ A[j]$が成り立ち、
$0 \le i < j \le M-1$を満たす全ての$(i, j)$組について、$B[i] ≠ B[j]$が成り立つ。
また、数列$A$,$B$のどの要素も$1$以上$N$以下の整数である。

ここで、「数列$X$に値$Y$が含まれる」を定義する。
数列$X$の要素の内、一つ以上の要素の値が$Y$であるとき、「数列$X$に値$Y$が含まれる」と定義する。
数列$X$のどの要素の値も$Y$でない場合、「数列$X$に値$Y$が含まれない」と定義する。

数列$B$の全ての要素に(一様に)$v$を加算した数列を$Bv$としたとき、
数列$A$にも数列$Bv$にも含まれるような整数値はいくつあるか求めよ。
(ただし$v$の変域は、$0 <= v <= Q-1$とする。)

入力

L M N
A[0] … A[L-1]
B[0] … B[M-1]
Q

$1 \le N \le 10^5$
$1 \le L \le N$
$1 \le M \le N$
$1 \le A[i] \le N$
$1 \le B[i] \le N$
$1 \le Q \le N$

追加制約:
subtask1 : $N \le 3000$, $Q = 1$
subtask2 : $N \le 3000$
subtask3 : $Q = 1$
subtask4 : 無し

出力

出力は$Q$行から成る。
$i+1$行目($i >= 0$)に、数列$A$にも数列$Bi$にも含まれるような整数値の数を出力せよ。
最後に改行してください。

サンプル

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

A = {1, 2, 3, 5} B0 = {1, 2}、AにもB0にも含まれる値は1と2
A = {1, 2, 3, 5} B1 = {2, 3}、AにもB1にも含まれる値は2と3
A = {1, 2, 3, 5} B2 = {3, 4}、AにもB2にも含まれる値は3
A = {1, 2, 3, 5} B3 = {4, 5}、AにもB3にも含まれる値は5
A = {1, 2, 3, 5} B4 = {5, 6}、AにもB4にも含まれる値は5

サンプル2
入力
11 11 32
1 4 7 10 13 16 19 22 25 28 30
1 2 4 6 8 12 16 24 27 28 29
1
出力
4

サンプル3
入力
5 6 210
1 2 5 210 15
5 4 2 7 10 3
5
出力
2
1
1
1
0

条件を満たす値が存在しない場合もあります。

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