問題一覧 > 通常問題

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[L1]、長さMの数列B=B[0],B[1],,B[M1]がある。
数列A, Bはそれぞれ、重複する要素がない数列である。すなわち、
0i<jL1を満たす全ての(i,j)組について、A[i]A[j]が成り立ち、
0i<jM1を満たす全ての(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<=Q1とする。)

入力

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

1N105
1LN
1MN
1A[i]N
1B[i]N
1QN

追加制約:
subtask1 : N3000, Q=1
subtask2 : N3000
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もしくは右上の雲マークをクリックしてアカウントを作成してください。