AT_arc014_4 [ARC014D] grepマスター

[problemUrl]: https://atcoder.jp/contests/arc014/tasks/arc014_4 高橋君は目$ 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_i $ は $ L_i\ を満たす。 $ 10. $ N+2 $ 行目から $ N+M+1 $ 行までの $ M $ 行では、$ L_i $ に対する各クエリを表す整数 $ x_i,\ y_i(0≦x_i,\ y_i≦10^9) $ が与えられる。 各クエリ$ x,\ y $ に対して表示される行数をそれぞれ$ 1 $ 行で出力すること。 また、出力の最後には改行をいれること。 ``` 7 2 3 2 4 1 1 3 0 3 4 ``` ``` 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 $行が答えとなる。 ``` 100 5 5 3 18 24 57 90 1 8 27 0 15 16 22 3 2 2 ``` ``` 46 80 98 79 25 ```

N/A

N/A