D - grepマスター
Editorial
/
高橋君は目grepが得意である。しかしこの世には目grepが得意な人が大勢いて特技にならないため、高橋君は新たな技を習得すべくgrepコマンドのマニュアルを目grepしていた。
検索コマンド grep には -B と -A というオプションがある。これは、
同じ行番号の行が複数回表示されることになった場合、これらはマージされ、全体で1回ずつしか現れないようになる。この挙動については出力例の説明が詳しい。
今、ファイルkakikomi.txt に対してあるパターンでgrepを実行し、ヒットする行番号のリスト L_1,L_2,...,L_n がわかっているものとする。ここに m 個のクエリが与えられ、それぞれx,yが指定される。各クエリについて、-B x -A yのオプションをつけて同様にgrepを実行した場合、表示される行数を答えよ。
入力は以下の形式で標準入力から与えられる。
各クエリx, y に対して表示される行数をそれぞれ1 行で出力すること。
また、出力の最後には改行をいれること。
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
検索コマンド 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 行目には kakikomi.txt の行数を表す整数 all(1≦all≦10^9)、ヒットした行数を表す整数 N(1≦N≦min(all,10^5)) 、クエリx, y の個数を表す整数 M(1≦M≦10^5) が与えられる。
- 2 行目から N+1 行までの N 行では、i 番目にヒットした行の行番号を表す整数 L_{i}(1≦L_{i}≦all) が与えられる。
- L_i は L_i < L_{i+1}を満たす。
- N+2 行目から N+M+1 行までの M 行では、L_i に対する各クエリを表す整数 x_i, y_i(0≦x_i, y_i≦10^9) が与えられる。
出力
また、出力の最後には改行をいれること。
入力例 1
7 2 3 2 4 1 1 3 0 3 4
出力例 1
5 4 7
- ヒットした行は、 2 行目と 4 行目である。
- x = 1, y = 1 のとき、それぞれのヒット範囲は、 1 ~ 3 行目、3 ~ 5 行目なので、合わせて 5行が答えとなる。
- x = 3, y = 0 のとき、それぞれのヒット範囲は、 1 ~ 2 行目、1 ~ 4 行目なので、合わせて 4行が答えとなる。
- x = 3, y = 4 のとき、それぞれのヒット範囲は、 1 ~ 6 行目、1 ~ 7 行目なので、合わせて 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