#P17572. [JAG 2026 Summer Camp #3] Ants Sort
[JAG 2026 Summer Camp #3] Ants Sort
Problem Description
Consider a line segment whose left and right endpoints are walls located at coordinates and , respectively. The positive direction is to the right.
There are ants on the line segment, numbered from left to right. The -th ant is initially located at coordinate ; thus, . It carries the ball numbered and initially faces left if is L, and right if is R.
At time , all ants start moving in the direction they are facing at a speed of unit per second.
When an ant collides with a wall, it immediately reverses its direction. When two ants collide, both immediately reverse direction. At that moment, you may choose whether or not to swap the balls they are carrying.
Your goal is to make the -th ant carry the ball numbered for every (). It can be proven that this goal can always be achieved. Find the earliest time at which this can be achieved.
Input Format
The input consists of a single test case of the following format.
N M
X_1 P_1 D_1
X_2 P_2 D_2
...
X_N P_N D_N
The first line contains two integers and (, , and is even), representing the number of ants and the coordinate of the right wall, respectively.
For each (), the -th of the following lines contains two integers and , and a character , representing the initial coordinate of the -th ant, the number of the ball it is initially carrying, and its initial direction, respectively. The coordinates are even integers satisfying . The sequence is a permutation of and is not equal to . Each is either L or R.
Output Format
Print the earliest time at which this goal can be achieved. It is guaranteed that the answer is an integer.
3 10
2 3 R
4 1 R
8 2 L
7
2 943168
168 2 L
874 1 R
942815
9 168598874
2 2 L
4 9 R
8 4 L
16 3 L
32 1 R
64 6 R
128 8 R
256 5 R
512 7 L
168598856