2185E.md (2674B)
1 Source: https://codeforces.com/problemset/problem/2185/E 2 3 E. The Robotic Rush 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There exists an infinitely long number line. 22 23 On the number line, there are $n$ robots and $m$ spikes, each located at a specific point on the number line. The $i$-th robot is located at position $a_i$, and the $i$-th spike is located at position $b_i$. If a robot touches a spike, it dies. 24 25 $k$ instructions are transmitted to the robots, with each instruction being to either move left by one unit or to move right by one unit. 26 27 For each value $i$ ($1 \leq i \leq k$), output how many robots are still alive after the first $i$ instructions have been processed. 28 29 Input 30 31 The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 32 33 The first line of each test case contains three integers $n, m, k$ ($1 \le n, m, k \le 2 \cdot 10^5$) — the number of robots, spikes, and instructions respectively. 34 35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the locations of the robots. It is guaranteed that all elements of $a$ are distinct. 36 37 The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0 \le b_i \le 10^9$) — the locations of the spikes. It is guaranteed that all elements of $b$ are distinct. 38 39 The fourth line contains a string of length $k$ — the instructions transmitted to the robots. Each character is either $\texttt{L}$, representing an instruction to move to the left, or $\texttt{R}$, representing an instruction to move to the right. 40 41 It is guaranteed that the sum of each of $n, m, k$ over all test cases does not exceed $2 \cdot 10^5$. 42 43 Additional constraint: it is guaranteed that there are no robots and spikes at the same position. 44 45 Output 46 47 Output $k$ integers, where the $i$-th integer indicates how many robots are alive after the first $i$ instructions have been processed. 48 49 For Python users, make sure to select PyPy3 / PyPy2 (depending on which version of Python you're using) instead of Python3 or Python2 when submitting. 50 51 Example 52 53 Input 54 55 ``` 56 3 57 58 2 1 3 59 60 0 1 61 62 2 63 64 LRR 65 66 2 3 3 67 68 2 4 69 70 1 3 5 71 72 LRL 73 74 3 2 3 75 76 1 3 7 77 78 9 6 79 80 RRL 81 ``` 82 83 Output 84 85 ``` 86 2 2 1 87 88 0 0 0 89 90 3 2 2 91 ``` 92 93 Note 94 95 For the first test case: 96 97 * The first robot will move to positions $0 \rightarrow -1 \rightarrow 0 \rightarrow 1$, so it will not die. 98 * The second robot will move to positions $1 \rightarrow 0 \rightarrow 1 \rightarrow 2$, so it will die after processing the third instruction, since there is a spike at position $2$. 99 100 For the second test case, both robots will die after moving once.