codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.