Overview

This problem asks us to find the total training points each member earns over \(W\) weeks. Points consist of “number of visit days + bonus from visits during campaign periods.” By exploiting the fact that there are only 7 types of weekdays and tallying the number of campaign days per weekday, we can solve this efficiently.

Analysis

Key Insight

Decomposition of points: The points a member earns by visiting on the \(k\)-th overall day is \(1 + c\) (where \(c\) is the number of campaigns applicable on that day), so the total points can be decomposed as follows:

\[\text{Total Points} = \underbrace{\text{Number of visit days (base points)}}_{\text{days\_per\_week} \times W} + \underbrace{\text{Campaign bonus}}_{\text{Sum of visit days during each campaign period}}\]

Problem with the Naive Approach

Since \(W\) can be up to \(10^9\), simulating each of the \(7W\) days (up to 7 billion days) one by one is impossible.

Key to the Solution: There Are Only 7 Types of Weekdays

A member’s visit pattern is determined solely by the day of the week. In other words, the number of days a member visits during campaign \([S_j, E_j]\) can be found by summing “how many times weekday \(d\) appears in the interval \([S_j, E_j]\)” for each weekday they visit.

Furthermore, aggregating across all campaigns: $\(\text{Bonus} = \sum_{d \in \text{set of visiting weekdays}} \text{total\_camp}[d]\)\( where \)\text{total_camp}[d]\( is "the total number of times weekday \)d$ appears across all campaign periods combined.”

Algorithm

1. Tally campaign days per weekday:
   For each campaign \([S_j, E_j]\), calculate how many times weekday \(d\) (\(1 \leq d \leq 7\)) appears within the interval, and add it to total_camp[d].
   The number of occurrences of weekday \(d\) in the interval \([S, E]\) is the count of integers \(k\) satisfying \(k \equiv d \pmod{7}\), which can be computed in \(O(1)\).

2. Compute the answer for each member:

   • Base points \(= \text{days\_per\_week} \times W\)
   • Bonus \(= \sum_{d \in \text{visiting weekdays}} \text{total\_camp}[d]\)
   • Answer \(= \text{base points} + \text{bonus}\)

Concrete Example

A member with \(L=6, R=2\) visits on weekdays \(\{6,7,1,2\}\) (4 days per week). If \(W=3\): - Base points \(= 4 \times 3 = 12\) - Bonus \(= \text{total\_camp}[6] + \text{total\_camp}[7] + \text{total\_camp}[1] + \text{total\_camp}[2]\)

Complexity

• Time complexity: \(O(7M + 7N) = O(M + N)\)
  • 7 weekday calculations per campaign, up to 7 weekday additions per member
• Space complexity: \(O(N + M)\)

Implementation Notes

• Counting a specific weekday within an interval: The number of times weekday \(d\) appears in interval \([S, E]\) can be found by creating a function that counts the number of \(k\) in \([1, X]\) satisfying \(k \bmod 7 = t\) (where \(t = d \bmod 7\)), then computing \(\text{cnt}(E) - \text{cnt}(S-1)\).

• Weekday set when \(L > R\): Since the interval wraps around, handle it by combining range(L, 8) and range(1, R+1).

• \(W\) is large, but base points are just a simple multiplication, so this is not an issue. The number of campaigns \(M\) is at most \(2 \times 10^5\), so tallying per weekday is sufficiently fast.

  Source Code

import sys
from itertools import accumulate

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    members = []
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        members.append((L, R))
    
    campaigns = []
    for j in range(M):
        S = int(input_data[idx]); idx += 1
        E = int(input_data[idx]); idx += 1
        campaigns.append((S, E))
    
    # For each member, we need:
    # 1) Base points = number_of_days_per_week * W (each visit gives 1 point)
    # 2) Campaign bonus: for each campaign [S, E], count how many days in [S, E] 
    #    the member visits the gym.
    
    # Member i visits on days where (k-1) % 7 + 1 is in their day set.
    # If L <= R: days {L, L+1, ..., R}
    # If L > R: days {L, L+1, ..., 7, 1, 2, ..., R}
    
    # For a campaign [S, E], we need to count visits of member i in that range.
    # A member visits day k if day_of_week(k) is in their set.
    # day_of_week(k) = (k-1) % 7 + 1, i.e., 1-indexed.
    
    # Count of day d (1..7) in range [S, E]:
    # We need count of k in [S, E] where (k-1)%7 = d-1, i.e., k ≡ d (mod 7) (with 7≡0 mapped to 7)
    # Actually k mod 7: k=1->1, k=2->2, ..., k=7->0. Let's use (k-1)%7 giving 0..6 for days 1..7.
    
    # For range [S, E], count of k where (k-1)%7 = r (r=0..6):
    # This is count of k in [S, E] where k ≡ r+1 (mod 7).
    # = floor((E - (r+1))/7) + 1 if r+1 adjusted to be in [S, E], else ...
    # Let's use: count of integers in [S, E] ≡ t (mod 7) where t in {1,...,7}, treat 7 as 0.
    
    # Precompute for each campaign, the count of each weekday in [S, E].
    # Then for each member, sum over campaigns the count of their active weekdays.
    
    # But N, M up to 2e5, and weekdays only 7, so we can:
    # For each weekday d (1..7), compute total campaign-day count across all campaigns.
    # Then for each member, bonus = sum over d in their set of total_campaign_count[d].
    
    # count of k in [S,E] with weekday d: 
    # weekday d means (k-1)%7 = d-1, i.e., k ≡ d (mod 7) (where d=7 means k≡0 mod 7)
    
    def count_weekday_in_range(S, E, d):
        # count of k in [S, E] such that (k-1) % 7 == d-1
        # equivalently k % 7 == d % 7
        # Let t = d % 7  (so d=7 -> t=0, d=1 -> t=1, etc.)
        t = d % 7
        # count of k in [S, E] with k%7 == t
        # = floor(E/7)*7 adjusted...
        # Use: count in [1, X] with k%7==t: if t==0: floor(X/7), else floor((X-t)/7)+1 if t<=X else 0
        def cnt(X):
            if X <= 0:
                return 0
            if t == 0:
                return X // 7
            else:
                if t > X:
                    return 0
                return (X - t) // 7 + 1
        return cnt(E) - cnt(S - 1)
    
    # Accumulate total campaign counts per weekday
    total_camp = [0] * 8  # index 1..7
    for S, E in campaigns:
        for d in range(1, 8):
            total_camp[d] += count_weekday_in_range(S, E, d)
    
    out = []
    for L, R in members:
        # days per week
        if L <= R:
            days_per_week = R - L + 1
            day_set = range(L, R + 1)
        else:
            days_per_week = 7 - L + 1 + R
            day_set = list(range(L, 8)) + list(range(1, R + 1))
        
        base = days_per_week * W
        bonus = 0
        for d in day_set:
            bonus += total_camp[d]
        
        out.append(str(base + bonus))
    
    sys.stdout.write('\n'.join(out) + '\n')

solve()

---

This editorial was generated by claude4.6opus-thinking.