← 返回题目列表

Codeforces · 2185/E

E. 机器人热潮

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

存在一条无限长的数轴。

在数轴上,有 $$$n$$$ 个机器人和 $$$m$$$ 尖峰,每个尖峰位于数轴上的特定点。第 $$$i$$$ 个机器人位于位置 $$$a_i$$$,第 $$$i$$$ 个尖峰位于位置 $$$b_i$$$。如果机器人碰到尖刺,它就会死亡。

$$$k$$$指令被传送到机器人,每个指令要么向左移动一个单位,要么向右移动一个单位。

对于每个值 $$$i$$$ ($$$1 \leq i \leq k$$$),输出在处理第一个 $$$i$$$ 指令后仍然存活的机器人数量。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n, m, k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^5$$$) — 分别是机器人、尖峰和指令的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 机器人的位置。保证 $$$a$$$ 的所有元素都是不同的。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \le b_i \le 10^9$$$) — 尖峰的位置。保证 $$$b$$$ 的所有元素都是不同的。

第四行包含长度为 $$$k$$$ 的字符串 — 传输到机器人的指令。每个字符要么是$$$\texttt{L}$$$,表示向左移动的指令,要么是$$$\texttt{R}$$$,表示向右移动的指令。

保证所有测试用例中每个 $$$n, m, k$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

附加约束:保证同一位置没有机器人和尖刺。

输出

输出 $$$k$$$ 个整数,其中第 $$$i$$$ 个整数表示在处理第一个 $$$i$$$ 指令后有多少机器人处于活动状态。

对于 Python 用户,请确保在提交时选择 PyPy3 / PyPy2(取决于您使用的 Python 版本)而不是 Python3 或 Python2。

示例

输入
复制

3
2 1 3
0 1
2
LRR
2 3 3
2 4
1 3 5
LRL
3 2 3
1 3 7
9 6
RRL

输出
复制

2 2 1
0 0 0
3 2 2

注意

对于第一个测试用例:

  • 第一个机器人会移动到位置$$$0 \rightarrow -1 \rightarrow 0 \rightarrow 1$$$,所以它不会死。
  • 第二个机器人将移动到位置 $$$1 \rightarrow 0 \rightarrow 1 \rightarrow 2$$$,因此在处理第三条指令后它将死亡,因为位置 $$$2$$$ 处有一个尖峰。

对于第二个测试用例,两个机器人都会在移动一次后死亡。