D. grep 大师 · AC 题库

第 14 场 AtCoder Regular Contest

grep 大师

grepマスター

AtCoder

⌀ 1904

原题

← C→

grep 大师AI (CI翻译)

grep

grepAI (CI翻译)

grep

grepAI (CI翻译)

grep

grepAI (CI翻译)

grep

grepAI (CI翻译)

grep

grepAI (CI翻译)

-B

-BAI (CI翻译)

-A

-AAI (CI翻译)

grep -B x -A y "needle" kakikomi.txt

grep -B x -A y "needle" kakikomi.txt

AI (CI翻译)

kakikomi.txt

kakikomi.txtAI (CI翻译)

"needle"

"needle"AI (CI翻译)

xAI (CI翻译)

yAI (CI翻译)

x,y

x,yAI (CI翻译)

kakikomi.txt

kakikomi.txtAI (CI翻译)

grep

grepAI (CI翻译)

L_1,L_2,...,L_n

L_1,L_2,...,L_nAI (CI翻译)

mAI (CI翻译)

-B

-BAI (CI翻译)

xAI (CI翻译)

-A

-AAI (CI翻译)

yAI (CI翻译)

grep

grepAI (CI翻译)

all N M
L_{1}
L_{2}
:
L_{N}
x_{1} y_{1}
x_{2} y_{2}
:
x_{M} y_{M}

all N M
L_{1}
L_{2}
:
L_{N}
x_{1} y_{1}
x_{2} y_{2}
:
x_{M} y_{M}

AI (CI翻译)

$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)$ が与えられる。
$N+2$ 行目から $N+M+1$ 行までの $M$ 行では、 $L_i$ に対する各クエリを表す整数 $x_i, y_i(0≦x_i, y_i≦10^9)$ が与えられる。

第 $1$ 行给出一个整数 $all(1≦all≦10^9)$ ，表示 $kakikomi.txt$ 的行数；一个整数 $N(1≦N≦min(all,10^5))$ ，表示匹配的行数；以及一个整数 $M(1≦M≦10^5)$ ，表示查询 $(x,y)$ 的数量。
第 $2$ 行至第 $N+1$ 行共 $N$ 行，给出整数 $L_{i}(1≦L_{i}≦all)$ ，表示第 $i$ 个匹配行的行号。
第 $N+2$ 行至第 $N+M+1$ 行共 $M$ 行，给出整数 $x_i, y_i(0≦x_i, y_i≦10^9)$ ，表示针对 $L_i$ 的各项查询。

AI (CI翻译)

x, y

对于每组 $x, y$ ，输出AI (CI翻译)

1AI (CI翻译)

AI (CI翻译)

5
4
7

5
4
7

AI (CI翻译)

ヒットした行は、 $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$ 行和第 $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$ 行。

AI (CI翻译)

AI (CI翻译)

AI (CI翻译)

题目信息

题号

arc014_4

所属比赛

第 14 场 AtCoder Regular Contest

时间限制

4 s

内存限制

256 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。