Overview

This problem asks us to calculate the total training points each member earns over \(W\) weeks, given each member’s weekly gym attendance pattern and campaign periods (ranges of consecutive days).

Analysis

Naive Approach and Its Limitations

Since the number of weeks \(W\) can be up to \(10^9\) (meaning up to \(7 \times 10^9\) business days), simulating day by day to calculate points would result in a Time Limit Exceeded (TLE) verdict. Additionally, since the number of members \(N\) and campaigns \(M\) can each be up to \(2 \times 10^5\), individually checking the overlap between each member and every campaign is also infeasible.

Key Insight

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

Of these, base points are very easy to calculate. If member \(i\) visits the gym \(D_i\) days per week, the base points earned over \(W\) weeks is simply \(W \times D_i\).

The challenge is calculating the campaign points. Here, we note that one week repeats in a short cycle of 7 days. For each campaign \(j\) with period \([S_j, E_j]\), we can count “how many times each day of the week (day \(1\) through day \(7\)) is included in that period.”

Let \(tot[d]\) be the total number of times day \(d\) (\(1 \leq d \leq 7\)) is included in a campaign period across all campaigns. If this is precomputed, the campaign points earned by member \(i\) can be quickly determined as the sum of \(tot[d]\) over all days of the week that member \(i\) visits.

Furthermore, since the attendance pattern \((L_i, R_i)\) satisfies \(1 \leq L_i, R_i \leq 7\), there are at most \(7 \times 7 = 49\) possible patterns. Therefore, if we precompute the “base points (number of days per week)” and “campaign points (sum of \(tot[d]\) for attended days)” for all 49 patterns (creating a lookup table), we can answer each member’s query in \(O(1)\).

Fast Counting of Day-of-Week Occurrences Within a Campaign Period

We consider how to calculate in \(O(1)\) how many times a specific day of the week \(d\) appears within a campaign period \([S_j, E_j]\). For 0-indexed computation, we use the half-open interval \([s, e) = [S_j - 1, E_j)\).

The number of times day \(d\) (\(1 \leq d \leq 7\)) has occurred by the \(x\)-th cumulative day can be expressed using the quotient \(q\) and remainder \(r\) of dividing \(x\) by 7 (i.e., \(x = 7q + r\)): $\(\text{count}(x, d) = q + \begin{cases} 1 & (d \leq r) \\ 0 & (d > r) \end{cases}\)$

Using this, the number of occurrences of day \(d\) in the interval \([s, e)\) can be computed in \(O(1)\) as the following difference: $\(\text{count}(e, d) - \text{count}(s, d)\)$

By summing this over all campaigns (\(M\) in total) for each day \(d \in \{1, \dots, 7\}\), we can construct the array \(tot\) in \(O(M)\).

Algorithm

1. Campaign Aggregation:

   • Initialize an array \(tot\) of size 8 with zeros (using 1-indexed to manage days \(1\) through \(7\)).
   • For each campaign \(j = 1, \dots, M\):
     • Set \(s = S_j - 1\), \(e = E_j\).
     • Compute the quotient and remainder of dividing \(s\) and \(e\) by 7:

          - `q_s, r_s = divmod(s, 7)`
          - `q_e, r_e = divmod(e, 7)`
       

     • For each day \(d \in \{1, \dots, 7\}\), calculate the number of occurrences within the period and add it to \(tot[d]\).

2. Pattern Precomputation:

   • Prepare \(7 \times 7\) two-dimensional arrays days_val and camp_val.
   • For all pairs \(L, R \in \{1, \dots, 7\}\):
     • Enumerate the days from \(L\) to \(R\) (considering wraparound), record the count as days_val[L][R], and record the sum of \(tot[d]\) for those days as camp_val[L][R].

3. Computing the Answer for Each Member:

   • For each member \(i = 1, \dots, N\), the answer is computed as follows: $\(\text{Earned points} = W \times \text{days\_val}[L_i][R_i] + \text{camp\_val}[L_i][R_i]\)$
   • Output this value.

Complexity

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

  • Campaign aggregation: For each of the \(M\) campaigns, we loop 7 times, so \(O(7M) = O(M)\) time.
  • Pattern precomputation: For \(7 \times 7\) combinations, we scan at most 7 days each, so \(O(7^3) = O(1)\) time.
  • Per-member computation: For \(N\) members, each computed in \(O(1)\), so \(O(N)\) time.
  • Overall, this is \(O(N + M)\), which is well within the time limit.

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

  • \(O(N + M)\) memory is used to store input data and output results.
  • The arrays for aggregation and precomputation have constant size (at most \(8 \times 8\)), so additional space is \(O(1)\).

Implementation Notes

• Handling Large Values: Since \(W\) can be up to \(10^9\), the total points a member earns may require a 64-bit integer type (in Python, integers are automatically handled as arbitrary-precision).

• Handling Wraparound Intervals: When \(L_i > R_i\), the days wrap around the week. For example, when \(L_i = 6, R_i = 2\), the set of days is represented as \([6, 7] \cup [1, 2]\), wrapping around at \(7\) and concatenating the lists to correctly represent the set of days.

  Source Code

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    W = int(input_data[1])
    M = int(input_data[2])

    L_R = list(map(int, input_data[3 : 3 + 2 * N]))
    S_E = list(map(int, input_data[3 + 2 * N : 3 + 2 * N + 2 * M]))

    tot = [0] * 8

    for j in range(M):
        s = S_E[2 * j] - 1
        e = S_E[2 * j + 1]

        q_e, r_e = divmod(e, 7)
        q_s, r_s = divmod(s, 7)

        diff_q = q_e - q_s
        for d in range(1, 8):
            tot[d] += diff_q + (1 if d <= r_e else 0) - (1 if d <= r_s else 0)

    days_val = [[0] * 8 for _ in range(8)]
    camp_val = [[0] * 8 for _ in range(8)]

    for l in range(1, 8):
        for r in range(1, 8):
            if l <= r:
                days = list(range(l, r + 1))
            else:
                days = list(range(l, 8)) + list(range(1, r + 1))

            days_val[l][r] = len(days)
            camp_val[l][r] = sum(tot[d] for d in days)

    ans = []
    for i in range(N):
        l = L_R[2 * i]
        r = L_R[2 * i + 1]
        pt = W * days_val[l][r] + camp_val[l][r]
        ans.append(str(pt))

    print("\n".join(ans))


if __name__ == "__main__":
    main()

---

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