ACAC 题库 ac.isam.top
GitHub
第 475 场 AtCoder Beginner Contest
E
问答竞赛：晋级者
Quiz Competition: Qualifiers
AtCoder
⌀ 1737
原题
← DF →

问答竞赛：晋级者AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

A preliminary round of a quiz competition was held. There are $N$ participants, numbered $1$ to $N$, and at most $M$ of them can pass the preliminary round.

一场问答竞赛的预赛已经举行。共有 $N$ 名参赛者，编号为 $1$ 至 $N$，其中至多有 $M$ 人可以通过预赛。AI (CI翻译)

The preliminary round consists of $K$ two-choice quiz questions, and the answer to each question is o or x. Participant $i$'s answer to the $j$-th question is given as the $j$-th character of the string $S_i$. The correct answer to the $j$-th question is given as the $j$-th character of the string $T$.

预赛由 $K$ 道二选一的问答题组成，每道题的答案为 o 或 x。 参赛者 $i$ 对第 $j$ 道题的回答由字符串 $S_i$ 的第 $j$ 个字符给出。 第 $j$ 道题的正确答案由字符串 $T$ 的第 $j$ 个字符给出。AI (CI翻译)

The qualifiers are determined by the following procedure.

晋级者按照以下过程确定。AI (CI翻译)

  • Initially, the numbers of qualifiers and non-qualifiers are both $0$; all $N$ participants are undetermined.
  • For $k=1,2,\dots,K$ in this order, perform the following process.
  • If the number of qualifiers plus the number of undetermined participants who answered the $k$-th question correctly is at most $M$, then all undetermined participants who answered the $k$-th question correctly become qualifiers.
    • Otherwise, all undetermined participants who answered the $k$-th question incorrectly become non-qualifiers.
  • All remaining undetermined participants become non-qualifiers.
  • 初始时，晋级者和未晋级者的人数均为 $0$；$N$ 名参赛者全部处于未确定状态。
  • 按照 $k=1,2,\dots,K$ 的顺序，执行以下过程。
  • 如果晋级者人数与第 $k$ 道题回答正确的未确定参赛者人数之和不超过 $M$，则所有回答第 $k$ 道题正确的未确定参赛者都成为晋级者。
    • 否则，所有回答第 $k$ 道题错误的未确定参赛者都成为未晋级者。
  • 所有剩余的未确定参赛者都成为未晋级者。
AI (CI翻译)

You are given $Q$ queries in the following format. Process them in order.

接下来给出 $Q$ 个询问。请按顺序处理。AI (CI翻译)

  • Integers $i$ and $j$ are given. Change participant $i$'s answer to the $j$-th question from o to x, or from x to o. Then, determine whether participant $i$ passes the preliminary round.
  • 给出整数 $i$ 和 $j$。将参赛者 $i$ 对第 $j$ 道题的答案从 o 改为 x，或从 x 改为 o。然后，判断参赛者 $i$ 是否通过预赛。
AI (CI翻译)

The change of the answer in each query remains in effect when processing subsequent queries as well.

每次询问中答案的修改在处理后续询问时也会保持有效。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $1 \leq M \leq N \leq 3\times 10^4$
  • $1 \leq K \leq 200$
  • $S_i$ and $T$ are strings of length $K$ consisting of o and x.
  • $1 \leq Q \leq 5\times 10^4$
  • For each query, $1\leq i \leq N$ and $1 \leq j \leq K$.
  • $1 \leq M \leq N \leq 3\times 10^4$
  • $1 \leq K \leq 200$
  • $S_i$ 和 $T$ 是长度为 $K$ 且仅由 o 和 x 构成的字符串。
  • $1 \leq Q \leq 5\times 10^4$
  • 对于每个询问，$1\leq i \leq N$ 且 $1 \leq j \leq K$。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N M K
T
S_1
\vdots
S_N
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

N M K
T
S_1
\vdots
S_N
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
AI (CI翻译)

Here, $\mathrm{query}_q$ represents the $q$-th query, and is given in the following format:

其中，$\mathrm{query}_q$ 表示第 $q$ 个询问，格式如下：AI (CI翻译)

i j

i j
AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output $Q$ lines. The $q$-th line should contain Yes if the participant specified in the $q$-th query passes the preliminary round, and No otherwise.

输出 $Q$ 行。 第 $q$ 行应包含 Yes，如果第 $q$ 个询问中指定的参赛者通过了预赛；否则应包含 No。AI (CI翻译)

样例

Input #1
5 3 3
oxo
oxo
oxx
xxo
xox
xoo
3
5 1
1 3
4 1
Output #1
Yes
Yes
No
- Before the first query, participants $1,2$ pass on the first question and participant $3$ passes on the second question, so the qualifiers are the three participants $1,2,3$. - After the first query, participants $1,2,5$ pass on the first question, so the qualifiers are the three participants $1,2,5$. Since participant $5$ passes the preliminary round, output `Yes`. - After the second query, participants $1,2,5$ still pass on the first question, so the qualifiers are the three participants $1,2,5$. Since participant $1$ passes the preliminary round, output `Yes`. - After the third query, participant $3$ is eliminated on the first question, participants $1,2$ pass on the second question, and participant $5$ passes on the third question, so the qualifiers remain the three participants $1,2,5$. Since participant $4$ does not pass the preliminary round, output `No`.
Input #2
3 1 2
ox
xo
oo
ox
4
3 1
1 1
2 2
1 2
Output #2
No
No
Yes
No
Input #3
1 1 1
o
o
2
1 1
1 1
Output #3
No
Yes
题目信息
题号
abc475_e
所属比赛
第 475 场 AtCoder Beginner Contest
时间限制
2 s
内存限制
1024 MB

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