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

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 77
作問者 : startcppstartcpp

4 ProblemId : 440 / 出題時の順位表

問題文

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

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

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

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