AtCoder Regular Contest 014

D - grepマスター


Time limit時間制限 : 4sec / Memory limitメモリ制限 : 256MB

問題文

高橋君は目grepが得意である。しかしこの世には目grepが得意な人が大勢いて特技にならないため、高橋君は新たな技を習得すべくgrepコマンドのマニュアルを目grepしていた。

検索コマンド grep には -B-A というオプションがある。これは、
grep -B x -A y "needle" kakikomi.txt
とすると ファイルkakikomi.txt でパターン "needle" にヒットした行だけでなく、その行の直前 x 行, 直後 y 行をあわせて表示するというものである。直前直後にある行数がx,yに満たない場合、あるだけ表示する。

同じ行番号の行が複数回表示されることになった場合、これらはマージされ、全体で1回ずつしか現れないようになる。この挙動については出力例の説明が詳しい。

今、ファイルkakikomi.txt に対してあるパターンでgrepを実行し、ヒットする行番号のリスト L_1,L_2,...,L_n がわかっているものとする。ここに m 個のクエリが与えられ、それぞれx,yが指定される。各クエリについて、-B x -A yのオプションをつけて同様にgrepを実行した場合、表示される行数を答えよ。

入力

入力は以下の形式で標準入力から与えられる。
all N M
L_{1}
L_{2}
:
L_{N}
x_{1} y_{1}
x_{2} y_{2}
:
x_{M} y_{M}
  1. 1 行目には kakikomi.txt の行数を表す整数 all(1≦all≦10^9)、ヒットした行数を表す整数 N(1≦N≦min(all,10^5)) 、クエリx, y の個数を表す整数 M(1≦M≦10^5) が与えられる。
  2. 2 行目から N+1 行までの N 行では、i 番目にヒットした行の行番号を表す整数 L_{i}(1≦L_{i}≦all) が与えられる。
    • L_iL_i < L_{i+1}を満たす。
  3. N+2 行目から N+M+1 行までの M 行では、L_i に対する各クエリを表す整数 x_i, y_i(0≦x_i, y_i≦10^9) が与えられる。

出力

各クエリx, y に対して表示される行数をそれぞれ1 行で出力すること。
また、出力の最後には改行をいれること。

入力例 1

7 2 3
2
4
1 1
3 0
3 4

出力例 1

5
4
7
  • ヒットした行は、 2 行目と 4 行目である。
  • x = 1, y = 1 のとき、それぞれのヒット範囲は、 13 行目、35 行目なので、合わせて 5行が答えとなる。
  • x = 3, y = 0 のとき、それぞれのヒット範囲は、 12 行目、14 行目なので、合わせて 4行が答えとなる。
  • x = 3, y = 4 のとき、それぞれのヒット範囲は、 16 行目、17 行目なので、合わせて 7行が答えとなる。

入力例 2

100 5 5
3
18
24
57
90
1 8
27 0
15 16
22 3
2 2

出力例 2

46
80
98
79
25

Submit提出する