33OJ
登录 注册

#P17572. [JAG 2026 Summer Camp #3] Ants Sort

[JAG 2026 Summer Camp #3] Ants Sort

题目描述

有一条线段,其左、右端点分别是位于坐标 00 和 MM 处的墙壁。规定向右为正方向。

线段上有 NN 只蚂蚁,从左到右编号为 1,2,…,N1,2,\ldots,N。第 ii 只蚂蚁最初位于坐标 XiX_i,因此有 0<X1<X2<⋯<XN<M0<X_1<X_2<\cdots<X_N<M。它携带编号为 PiP_i 的球。当 DiD_i 为 L 时,它最初朝左;当 DiD_i 为 R 时,它最初朝右。

在时刻 00,所有蚂蚁同时开始以每秒 11 个单位长度的速度,沿各自朝向移动。

当一只蚂蚁撞到墙壁时,它会立即反向。当两只蚂蚁相撞时,它们都会立即反向。此时,你可以选择是否交换它们携带的球。

你的目标是使每个 ii(1≤i≤N1\le i\le N)对应的第 ii 只蚂蚁都携带编号为 ii 的球。可以证明,这一目标总能实现。求最早能够实现该目标的时刻。

输入格式

输入包含一组测试数据,格式如下。

N M
X_1 P_1 D_1
X_2 P_2 D_2
...
X_N P_N D_N

第一行包含两个整数 NN 和 MM(2≤N≤2×1052\le N\le2\times10^5,6≤M≤10156\le M\le10^{15},且 MM 为偶数),分别表示蚂蚁的数量和右侧墙壁的坐标。

对于每个 ii(1≤i≤N1\le i\le N),接下来 NN 行中的第 ii 行包含两个整数 Xi,PiX_i,P_i 和一个字符 DiD_i,分别表示第 ii 只蚂蚁的初始坐标、最初携带的球的编号,以及初始朝向。坐标 X1,X2,…,XNX_1,X_2,\ldots,X_N 均为偶数,满足 0<X1<X2<⋯<XN<M0<X_1<X_2<\cdots<X_N<M。序列 (P1,P2,…,PN)(P_1,P_2,\ldots,P_N) 是 (1,2,…,N)(1,2,\ldots,N) 的一个排列,且不等于 (1,2,…,N)(1,2,\ldots,N)。每个 DiD_i 均为 L 或 R。

输出格式

输出最早能够实现目标的时刻。保证答案为整数。

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