C - ビリヤードの反射 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、長さ M のビリヤード台の上でボールを転がします。ビリヤード台は一直線の区間 [0, M] で表されます。

ボールの初期位置は座標 S です。高橋君は N 回のショットを順番に行います。i 番目のショットは方向 C_i と距離 A_i で表されます。

  • C_i = L のとき、ボールを左向き（座標が減る方向）に距離 A_i だけ転がします。
  • C_i = R のとき、ボールを右向き（座標が増える方向）に距離 A_i だけ転がします。

ボールは区間 [0, M] の外には出ません。転がっている途中でボールが端点 0 または M に到達し、まだ移動距離が残っている場合、進行方向をただちに反転させて転がり続けます。この反転を 1 回の 反射 と呼びます。1 回のショットの中で反射は複数回発生することがあります。

また、あるショットの開始時点でボールが端点 0 にあり C_i = L である場合、または端点 M にあり C_i = R である場合は、移動距離を消費せずにただちに進行方向を反転させ、これも 1 回の反射と数えます。

ただし、A_i = 0 のショットでは、ボールの位置や方向にかかわらず、移動も反射も一切発生しません。

N 回のショットをすべて処理したときの、ボールの最終位置と、発生した反射の総回数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^9
  • 0 \leq S \leq M
  • C_i は L または R
  • 0 \leq A_i \leq 10^9
  • N, M, S, A_i はすべて整数である

入力

N M S
C_1 A_1
C_2 A_2
\vdots
C_N A_N
  • 1 行目には、ショットの回数を表す整数 N、台の長さを表す整数 M、ボールの初期位置を表す整数 S が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目のショットの方向を表す文字 C_i と、転がす距離を表す整数 A_i が、スペース区切りで与えられる。

出力

ボールの最終位置 P と、発生した反射の総回数 K を、この順にスペース区切りで 1 行に出力せよ。

入力例 1

3 10 4
R 3
L 5
R 8

出力例 1

10 0

入力例 2

4 5 0
L 2
R 3
R 1
L 0

出力例 2

4 2

入力例 3

10 17 8
R 12
L 4
L 20
R 0
R 35
L 1
R 17
L 18
R 5
L 33

出力例 3

17 7

入力例 4

20 1000000000 123456789
R 987654321
L 1000000000
R 1
R 999999999
L 500000000
L 750000000
R 250000000
L 0
R 1000000000
L 999999998
R 333333333
L 666666666
R 123456789
L 987654321
R 400000000
R 600000000
L 100000000
R 900000000
L 800000000
R 700000000

出力例 4

713580243 10

入力例 5

1 1 0
L 0

出力例 5

0 0

Score : 366 pts

Problem Statement

Takahashi rolls a ball on a billiard table of length M. The billiard table is represented as a one-dimensional interval [0, M].

The initial position of the ball is at coordinate S. Takahashi performs N shots in order. The i-th shot is represented by a direction C_i and a distance A_i.

  • If C_i = L, the ball is rolled to the left (in the direction of decreasing coordinate) by a distance of A_i.
  • If C_i = R, the ball is rolled to the right (in the direction of increasing coordinate) by a distance of A_i.

The ball never leaves the interval [0, M]. If, while rolling, the ball reaches an endpoint 0 or M and there is still remaining travel distance, the direction of travel is immediately reversed and the ball continues rolling. This reversal is called one reflection. Multiple reflections may occur within a single shot.

Additionally, if at the start of a shot the ball is at endpoint 0 and C_i = L, or at endpoint M and C_i = R, the direction of travel is immediately reversed without consuming any travel distance, and this also counts as one reflection.

However, for a shot with A_i = 0, regardless of the ball's position or direction, no movement or reflection occurs at all.

Find the final position of the ball and the total number of reflections that occurred after processing all N shots.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^9
  • 0 \leq S \leq M
  • C_i is L or R
  • 0 \leq A_i \leq 10^9
  • N, M, S, A_i are all integers

Input

N M S
C_1 A_1
C_2 A_2
\vdots
C_N A_N
  • The first line contains an integer N representing the number of shots, an integer M representing the length of the table, and an integer S representing the initial position of the ball, separated by spaces.
  • The i-th of the following N lines contains a character C_i representing the direction of the i-th shot and an integer A_i representing the rolling distance, separated by a space.

Output

Output the final position P of the ball and the total number of reflections K, in this order, separated by a space on a single line.

Sample Input 1

3 10 4
R 3
L 5
R 8

Sample Output 1

10 0

Sample Input 2

4 5 0
L 2
R 3
R 1
L 0

Sample Output 2

4 2

Sample Input 3

10 17 8
R 12
L 4
L 20
R 0
R 35
L 1
R 17
L 18
R 5
L 33

Sample Output 3

17 7

Sample Input 4

20 1000000000 123456789
R 987654321
L 1000000000
R 1
R 999999999
L 500000000
L 750000000
R 250000000
L 0
R 1000000000
L 999999998
R 333333333
L 666666666
R 123456789
L 987654321
R 400000000
R 600000000
L 100000000
R 900000000
L 800000000
R 700000000

Sample Output 4

713580243 10

Sample Input 5

1 1 0
L 0

Sample Output 5

0 0