← 返回题目列表

AtCoder · arc014_4

D. grep大师

中文机器翻译题面 查看原题

問題文

高桥有眼睛grep擅长。但这世界没有眼睛 擅长grep的人很多,而且这并不是什么特殊技能,所以高桥开始学习一项新技能。grep查看命令手册。grep是。

搜索命令 grep 有 有一个名为 -B 和 -A 的选项。这是
grep -B x -A y "needle" kakikomi.txt
文件 带有kakikomi.txt 的模式 不仅是命中 "needle" 的行,而且就在该行之前。 x 行, 直後 y 这些行一起显示。紧接之前和之后的行数 如果小于x,y,则显示尽可能多的内容。

如果具有相同行号的行多次出现,它们将被合并,以便每行仅出现一次。输出示例中详细解释了此行为。

现在文件 具有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 < 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 ,每个命中范围是 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