33OJ
登录 注册

#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 00 and MM, respectively. The positive direction is to the right.

There are NN ants on the line segment, numbered 1,2,…,N1,2,\ldots,N from left to right. The ii-th ant is initially located at coordinate XiX_i; thus, 0<X1<X2<⋯<XN<M0<X_1<X_2<\cdots<X_N<M. It carries the ball numbered PiP_i and initially faces left if DiD_i is L, and right if DiD_i is R.

At time 00, all ants start moving in the direction they are facing at a speed of 11 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 ii-th ant carry the ball numbered ii for every ii (1≤i≤N1\le i\le N). 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 NN and MM (2≤N≤2×1052\le N\le 2\times10^5, 6≤M≤10156\le M\le10^{15}, and MM is even), representing the number of ants and the coordinate of the right wall, respectively.

For each ii (1≤i≤N1\le i\le N), the ii-th of the following NN lines contains two integers XiX_i and PiP_i, and a character DiD_i, representing the initial coordinate of the ii-th ant, the number of the ball it is initially carrying, and its initial direction, respectively. The coordinates X1,X2,…,XNX_1,X_2,\ldots,X_N are even integers satisfying 0<X1<X2<⋯<XN<M0<X_1<X_2<\cdots<X_N<M. The sequence (P1,P2,…,PN)(P_1,P_2,\ldots,P_N) is a permutation of (1,2,…,N)(1,2,\ldots,N) and is not equal to (1,2,…,N)(1,2,\ldots,N). Each DiD_i 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