Overview

This problem asks us to calculate the total training points each member earns during a \(W\)-week operating period.

The points each member earns can be divided into “base points from the number of days attended (1 point per day)” and “bonus points from campaigns (1 point per visit during a campaign).” By leveraging the fact that days of the week repeat in a 7-day cycle, we can pre-aggregate the bonus points for each day of the week, allowing us to efficiently compute each member’s points.

Analysis

1. Limitations of Naive Simulation

The number of operating days can reach up to \(7 \times W = 7 \times 10^9\) days. Therefore, simulating who visits each day or scanning each campaign period day by day would exceed the time limit (TLE).

2. Separating Base Points and Bonus Points

The points earned by member \(i\) can be decomposed into the sum of the following two components: 1. Base points: The number of days the member visits the gym, regardless of campaigns (1 point per day) 2. Bonus points: The total number of times a visit falls within a campaign period (1 point per occurrence)

If we let \(len_i\) be the number of days member \(i\) visits per week, then since the operating period is \(W\) weeks, the base points are simply \(W \times len_i\) points.

3. Speedup Through Per-Day-of-Week Aggregation

The key observation for efficiently computing bonus points is that “whether a member visits the gym depends only on the ‘day of the week,’ not the absolute day number.”

A week has only \(7\) days. Therefore, if we can pre-compute “for each day of the week \(d\) (\(1 \le d \le 7\)), the total bonus points added by campaigns, Tot[d]”, then the bonus points for member \(i\) can be obtained in \(O(1)\) by simply summing up Tot[d] for the days of the week that member visits.

4. Computing the Number of Occurrences of a Day of the Week Within a Campaign Period

We need to efficiently determine how many times day of the week \(d\) appears within a campaign period \([S, E]\). By defining a function \(f(X, d)\) as “the number of times day of the week \(d\) appears from day \(1\) to day \(X\)”, the number of occurrences in the interval \([S, E]\) can be computed in \(O(1)\) as \(f(E, d) - f(S-1, d)\).

The number of times day of the week \(d\) appears up to day \(X\), \(f(X, d)\), can be calculated as follows: - \(q = \lfloor X / 7 \rfloor\) (the number of “complete weeks” contained within the first \(X\) days) - \(r = X \bmod 7\) (the remaining days)

Since day of the week \(d\) appears exactly once per week, it appears \(q\) times as a base. Additionally, if day of the week \(d\) is included in the remaining \(r\) days (i.e., when \(d \le r\)), it appears one more time. $\(f(X, d) = \begin{cases} q + 1 & (d \le r) \\ q & (d > r) \end{cases}\)$

Using this, we can compute the bonus points for each of the \(7\) days of the week in \(O(1)\) per campaign.

Algorithm

1. Initialization: Prepare an array Tot of length \(8\), initialized to all \(0\) (Tot[d] represents the total bonus points for day of the week \(d\)).
2. Processing Campaigns: For each campaign \([S_j, E_j]\), compute how many times each day of the week \(d \in \{1, 2, \dots, 7\}\) appears within the period, and add it to Tot[d].
3. Computing Points for Each Member: For each member \(i\), compute the following:
   • The number of days per week they visit, \(len_i\)
     • When \(L_i \le R_i\): \(R_i - L_i + 1\)
     • When \(L_i > R_i\): \(7 - L_i + 1 + R_i\)
   • The sum additional of Tot[d] for the days of the week that member \(i\) visits
   • Final earned points: \(W \times len_i + \text{additional}\)

Complexity

• Time Complexity: \(O(N + M)\)

  • Campaign processing: A loop of \(7\) iterations for each of the \(M\) campaigns, so \(O(M)\).
  • Member processing: A loop over the days visited (at most \(7\) days) for each of the \(N\) members, so \(O(N)\).
  • Overall, this runs sufficiently fast for the constraints \(N, M \le 2 \times 10^5\).

• Space Complexity: \(O(N)\)

  • \(O(N)\) memory is used for the array holding member information.
  • The array Tot holding bonus points per day of the week is a constant size of \(8\).

Implementation Notes

• Overflow Prevention: Since the number of operating weeks \(W\) can be up to \(10^9\), the maximum possible points can be approximately \(7 \times 10^9 \times (1 + M)\), which overflows 32-bit integers. In C++, you need to use 64-bit signed integer types such as long long.

• Handling Wrap-Around Intervals: When \(L_i > R_i\) (e.g., from day \(6\) to day \(2\) of the next week), the interval wraps around the week boundary. This can be implemented concisely by splitting it into two intervals \([L_i, 7]\) and \([1, R_i]\) and looping over each.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long W;
    int M;
    if (!(cin >> N >> W >> M)) return 0;

    vector<pair<int, int>> members(N);
    for (int i = 0; i < N; ++i) {
        cin >> members[i].first >> members[i].second;
    }

    // 各曜日 d (1 <= d <= 7) について、キャンペーンによって追加されるポイントの総和
    long long Tot[8] = {0};
    for (int j = 0; j < M; ++j) {
        long long S, E;
        cin >> S >> E;
        long long S_minus_1 = S - 1;
        
        long long qE = E / 7;
        long long rE = E % 7;
        long long qS = S_minus_1 / 7;
        long long rS = S_minus_1 % 7;

        for (int d = 1; d <= 7; ++d) {
            long long countE = qE + (d <= rE ? 1 : 0);
            long long countS = qS + (d <= rS ? 1 : 0);
            Tot[d] += (countE - countS);
        }
    }

    // 各会員の獲得ポイントを計算して出力
    for (int i = 0; i < N; ++i) {
        int L = members[i].first;
        int R = members[i].second;
        long long len = 0;
        long long additional = 0;
        if (L <= R) {
            len = R - L + 1;
            for (int d = L; d <= R; ++d) {
                additional += Tot[d];
            }
        } else {
            len = 7 - L + 1 + R;
            for (int d = L; d <= 7; ++d) {
                additional += Tot[d];
            }
            for (int d = 1; d <= R; ++d) {
                additional += Tot[d];
            }
        }
        long long ans = W * len + additional;
        cout << ans << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.