E - Shinkansen
問題文
umg くんは、 $1$ 両編成の新幹線を運営しています。
車内には座標 $0$ から座標 $W$ まで続く通路があり、左側の入口は座標 $0$、右側の入口は座標 $W$ にあります。
通路の幅は人 $1$ 人分であり、乗客同士はすれ違えません。
通路の脇には、各整数座標 $1,2,\ldots,W-1$ にそれぞれ $10^{100}$ 席の座席があります。
$N$ 人の乗客がこの新幹線に乗ろうとしています。乗客には $1$ から $N$ までの番号が付いており、乗客 $i$ は座標 $X_i$ にある座席に座る予定です。
乗客 $i$ は時刻 $T_i$ に、$S_i$ に応じて次の位置に現れます。
- $S_i$ が
Lのとき、左側の入口である座標 $0$。 - $S_i$ が
Rのとき、右側の入口である座標 $W$。
その後、 $1$ 単位時間に距離 $1$ 進む一定の速さで、座標 $X_i$ に向かって通路を歩きます。
座標 $X_i$ に到着すると、そこで $0.5$ 単位時間だけ立ち止まってから着席します。
到着した時刻にはまだ通路におり、着席した時刻以降は通路にいないものとします。
同じ時刻に通路にいる $2$ 人の乗客が同じ座標に来ると、衝突してけんかになります。
時刻や座標が整数でなくても、衝突することがあります。
umg くんはけんかを防ぐために、乗客を何人か選んで乗車をキャンセルしてもらうことにしました。選ぶ人数は $0$ 人でもかまいません。
残りの乗客の間で衝突が一度も起こらないようにするために、乗車をキャンセルしてもらう必要がある乗客の最小人数を求めてください。
制約
- $2 \leq N \leq 2 \times 10^5$
- $2 \leq W \leq 10^9$
- $1 \leq X_i < W$
- $1 \leq T_i \leq 10^9$
- $T_1,T_2,\ldots,T_N$ は相異なる
- $S_i$ は
LまたはRである - 入力される数値はすべて整数である
部分点
この問題には部分点が設定されています。
- $N \leq 20$ を満たすデータセットに正解した場合、 $200$ 点が与えられます。
入力
入力は以下の形式で標準入力から与えられます。
$N$ $W$
$T_1$ $X_1$ $S_1$
$\vdots$
$T_N$ $X_N$ $S_N$
出力
キャンセルしてもらう必要がある乗客の最小人数を出力してください。
3 10
1 1 L
2 2 R
3 9 L
1
全員が今回の新幹線に乗ると、それぞれ次のように行動します。
- 乗客 $1$ は時刻 $1$ に座標 $0$ に現れ、時刻 $2$ に座標 $1$ に到着し、時刻 $2.5$ に着席します。
- 乗客 $2$ は時刻 $2$ に座標 $10$ に現れ、時刻 $10$ に座標 $2$ に到着し、時刻 $10.5$ に着席します。
- 乗客 $3$ は時刻 $3$ に座標 $0$ に現れ、時刻 $12$ に座標 $9$ に到着し、時刻 $12.5$ に着席します。
このとき、乗客 $2$ と乗客 $3$ は時刻 $7.5$ に座標 $4.5$ で衝突します。
乗客 $2$ にキャンセルしてもらえば、残りの乗客の間で衝突は起こりません。
したがって、答えは $1$ です。
5 10
1 8 L
2 3 R
4 5 L
6 7 R
8 2 L
2
乗客 $2$ と乗客 $4$ にキャンセルしてもらえば、衝突は起こりません。
乗客 $1$ と乗客 $4$、乗客 $2$ と乗客 $3$ はそれぞれ衝突するため、 $1$ 人だけキャンセルしてすべての衝突を防ぐことはできません。
したがって、答えは $2$ です。
10 10
1 8 L
2 2 R
20 8 L
21 2 R
40 8 L
41 2 R
60 8 L
80 8 L
100 2 R
120 2 R
3