P15847 [NOISG 2026 Finals] Monkeys

Monkeyland is an infinite number line with $n$ monkeys, numbered from 1 to $n$. The $i$-th monkey is initially at position $p[i]$ on the number line. It is possible that multiple monkeys share the same initial position. Pan can make every monkey move with his enchanting spell! How each monkey moves is determined by a string $d$ of length $n$ where each character is either L or R. Let the $i$-th character of $d$ be $d[i]$. Once a spell is cast, the $i$-th monkey moves as follows: * If $d[i] = \text{L}$, it moves to the left by **one position**. * If $d[i] = \text{R}$, it moves to the right by **one position**. Each day, Pan will cast his spell exactly once. If two monkeys are at the same position on any day (even initially), they become **friends**. If Pan were to cast his spell for $k$ days, determine the number of **pairs of monkeys** that will become friends.

Your program must read from standard input. The first line of input contains two space-separated integers $n$ and $k$. The second line of input contains $n$ space-separated integers $p[1], p[2], \dots, p[n]$. The third line of input contains a string $d$ of $n$ characters $d[1], d[2], \dots, d[n]$.

Your program must print to standard output. Output one integer, the number of pairs of monkeys that will become friends. The output should contain only a single integer. Do not print any additional text such as `Enter a number` or `The answer is`.

### Sample Test Case 1 Explanation There are $n = 2$ monkeys and Pan casts the spell for $k = 1$ day only. On the first day, monkey 1 moves right from position 1 to position 2 while monkey 2 moves left from position 3 to position 2. Since they end up at the same position on the first day, they become friends. Hence, there is exactly 1 pair of monkeys that become friends. ### Sample Test Case 2 Explanation There are $n = 5$ monkeys and Pan casts the spell for $k = 67$ consecutive days. Since all monkeys have distinct initial positions and each monkey moves one position to the right each day when a spell is cast, no two monkeys will be at the same position on any day. Hence, no pairs of monkeys can become friends. ### Sample Test Case 5 Explanation There are $n = 4$ monkeys and Pan casts his spell for $k = 2$ consecutive days. Each figure below depicts Monkeyland as a number line showing positions from 1 to 6 **only**. The arrow above each monkey indicates the direction in which it will move after a spell is cast. On the 0-th day, the initial positions of all monkeys are shown in the figure below. Monkeys 2 and 3 which are already at position 4 become friends. :::align{center}  ::: After the spell has been cast on the 1-st day, the positions of all monkeys are shown in the figure below. Monkeys 3 and 4 meet at position $5$ and become friends. :::align{center}  ::: After the spell has been cast on the 2-nd day, the positions of all monkeys are shown in the figure below. No two monkeys meet on this day. :::align{center}  ::: Therefore, there are a total of $2$ pairs of monkeys that are friends: Monkeys $2$ and $3$, as well as monkeys $3$ and $4$. ### Subtasks For all test cases, the input will satisfy the following bounds: * $1 \le n \le 200\,000$ * $1 \le k \le 10^9$ * $1 \le p[i] \le 10^9$ for all $1 \le i \le n$ * $d[i]$ is either L or R for all $1 \le i \le n$ Your program will be tested on input instances that satisfy the following restrictions: | Subtask | Score | Additional constraints | |:-------:|:-----:|----------------------------------| | 0 | 0 | Sample test cases | | 1 | 6 | $n = 2$ | | 2 | 13 | $d[1] = d[2] = \cdots = d[n]$ | | 3 | 10 | $n, k \le 200$ | | 4 | 22 | $n, k \le 3000$ | | 5 | 18 | $n \le 3000$ | | 6 | 31 | No additional constraints |