Overview

This is a problem where, on a billiard table \([0, M]\), we need to find the ball’s position and the number of reflections after each shot.
Instead of simulating the distance one unit at a time, we treat reflections as “movement on a straight line,” processing each shot in \(O(1)\).

Observations

If we simulate reflections directly, in cases like \(M=1, A_i=10^9\), an extremely large number of reflections occur in just a single shot.
Since \(N\) can be up to \(2 \times 10^5\), processing reflections one at a time will not be fast enough.

The key idea is to imagine the billiard table mirrored infinitely to the left and right.

For example, when the table length is \(M\), the actual position can be expressed with period \(2M\) as follows:

• Let \(y\) be the coordinate on the infinite line
• Let \(r\) be the remainder when \(y\) is divided by \(2M\)
• If \(0 \leq r \leq M\), the actual position is \(r\)
• If \(M < r < 2M\), the actual position is \(2M-r\)

In other words, movement with reflections can be treated as straight movement on an infinite line.

For example, if the current position is \(pos\):

• Moving right by distance \(A\) corresponds to \(pos + A\) on the infinite line
• Moving left by distance \(A\) corresponds to \(pos - A\) on the infinite line

Then, by folding that coordinate back into \([0,M]\), we can determine the final position.

Meanwhile, the number of reflections can be counted as “the number of times a multiple of \(M\) is crossed on the infinite line.”
The endpoints \(0, M\) correspond to multiples of \(M\) on the infinite line: \(0, M, 2M, 3M, \dots\)

However, we need to be careful about the problem’s conditions:

• If the ball arrives exactly at an endpoint at the end of a shot, there is no remaining distance, so no reflection occurs
• If the ball starts at an endpoint and is hit outward, it immediately reflects, counting as 1
• However, if \(A_i=0\), no reflection or movement occurs at all

For this reason, we need to handle the boundaries of the interval for counting reflections carefully.

Algorithm

Let \(pos\) be the current position and \(total\) be the cumulative number of reflections.

For each shot, if \(A=0\), we skip and move to the next one.

Position Update

Consider a function that returns the actual position for a coordinate \(y\) on the infinite line.

The period is \(2M\).

\[ r = y \bmod 2M \]

However, since \(y\) can be negative, we adjust \(r\) so that \(0 \leq r < 2M\).

Then,

\[ \text{pos} = \begin{cases} r & (r \leq M) \\ 2M-r & (r > M) \end{cases} \]

gives the actual position after reflections.

For rightward movement, update with \(y=pos+A\); for leftward movement, update with \(y=pos-A\).

Counting Reflections

Rightward Case

When moving right by distance \(A\), we count the multiples of \(M\) contained in the interval

\[ [pos, pos+A) \]

on the infinite line.

The endpoint \(pos+A\) is excluded because if the distance is used up there, no reflection occurs.

In terms of integer intervals, we count multiples of \(M\) satisfying

\[ pos \leq kM \leq pos+A-1 \]

This can be computed with the following formula:

\[ \left\lfloor \frac{pos+A-1}{M} \right\rfloor - \left\lfloor \frac{pos-1}{M} \right\rfloor \]

However, if \(pos=0\) and moving rightward, the starting point \(0\) means we are moving inward, not outward, so it is not a reflection.
Therefore, in this case, we subtract \(1\).

Leftward Case

When moving left by distance \(A\), we count the multiples of \(M\) contained in the interval

\[ (pos-A, pos] \]

on the infinite line.

The endpoint \(pos-A\) is excluded.
On the other hand, the starting point is included because if it is outward-facing, it counts as an immediate reflection.

Therefore, the count is given by:

\[ \left\lfloor \frac{pos}{M} \right\rfloor - \left\lfloor \frac{pos-A}{M} \right\rfloor \]

However, if \(pos=M\) and moving leftward, moving left from starting point \(M\) is inward, so it is not a reflection.
Therefore, in this case, we subtract \(1\).

Processing Flow

For each shot, do the following:

1. If \(A=0\), skip
2. Compute the number of reflections in \(O(1)\) based on the direction
3. Fold the coordinate \(pos \pm A\) on the infinite line back into \([0,M]\) using the folding function
4. Add the number of reflections to the total

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Since each shot is processed in constant time, this is sufficiently fast.

Implementation Notes

C++ integer division for negative numbers truncates toward zero rather than performing the mathematical floor function \(\lfloor x/y \rfloor\).

In our formulas, values like \(pos-A\) can become negative, so we prepare a function floor_div that performs mathematical floor division.

ll floor_div(ll a, ll b) {
    if (a >= 0) return a / b;
    return - ((-a + b - 1) / b);
}

Also, the remainder when dividing a negative coordinate by \(2M\) can be negative with C++’s % operator.
Therefore, in the folding function, if the remainder is negative, we add \(2M\) to ensure \(0 \leq r < 2M\).

ll reflect_pos(ll y, ll M) {
    ll mod = 2 * M;
    ll r = y % mod;
    if (r < 0) r += mod;
    if (r <= M) return r;
    return 2 * M - r;
}

The cumulative number of reflections can become extremely large, so it is necessary to use the long long type.

Source Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll floor_div(ll a, ll b) {
    if (a >= 0) return a / b;
    return - ((-a + b - 1) / b);
}

ll reflect_pos(ll y, ll M) {
    ll mod = 2 * M;
    ll r = y % mod;
    if (r < 0) r += mod;
    if (r <= M) return r;
    return 2 * M - r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll M, pos;
    cin >> N >> M >> pos;

    ll total = 0;

    for (int i = 0; i < N; i++) {
        char C;
        ll A;
        cin >> C >> A;

        if (A == 0) continue;

        ll cnt = 0;

        if (C == 'R') {
            cnt = floor_div(pos + A - 1, M) - floor_div(pos - 1, M);
            if (pos == 0) cnt--;
            pos = reflect_pos(pos + A, M);
        } else {
            cnt = floor_div(pos, M) - floor_div(pos - A, M);
            if (pos == M) cnt--;
            pos = reflect_pos(pos - A, M);
        }

        total += cnt;
    }

    cout << pos << ' ' << total << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-medium.