Overview

This problem asks you to determine how many times each character is marked after performing \(K\) highlighter markings (each marking \(W\) consecutive characters) on a line of \(N\) characters. We solve this efficiently using the imos method (difference array).

Analysis

Naive Approach and Its Problems

The simplest method is to increment the count of \(W\) characters for each marking.

# Naive method (may result in TLE)
for _ in range(K):
    L = int(input())
    for j in range(L, L + W):
        count[j] += 1

This method requires \(O(W)\) processing for each marking, resulting in \(O(K \times W)\) overall. In the worst case, \(K = 2 \times 10^5\) and \(W = 2 \times 10^5\), requiring \(4 \times 10^{10}\) operations, which causes TLE (Time Limit Exceeded).

Solution Using the Imos Method

When there are multiple operations of “adding a uniform value to an interval,” the imos method (difference array) is effective.

Basic Idea: - Instead of adding \(+1\) to the interval \([L, L+W-1]\), record “\(+1\) at the start point, \(-1\) at the position after the end point” in a difference array - Taking the cumulative sum at the end gives the total value at each position

Concrete Example

For \(N = 10\), \(W = 3\), marking twice at \(L = 2\) and \(L = 4\):

Position:        1  2  3  4  5  6  7  8  9  10
Difference array: [0, +1, 0, 0, +1, -1, 0, -1, 0, 0, 0]
                  (+1 at L=2)  (+1 at L=4)(-1 at L+W=5)(-1 at L+W=7)

Cumulative sum:   [0, 1, 1, 1, 2, 1, 1, 0, 0, 0]

Positions 2, 3, 4 are marked once, and positions 4, 5, 6 are marked an additional time, so position 4 has a total of 2 markings.

Algorithm

1. Initialize difference array: Initialize array diff of size \(N+2\) with zeros
2. Record differences: For each marking \(L_i\):
   • Add \(+1\) to diff[L] (marking starts)
   • Add \(-1\) to diff[L + W] (position after marking ends)
3. Calculate cumulative sum: Take the cumulative sum of diff and output values from position \(1\) to \(N\)

diff[L] += 1      # Marking starts at position L
diff[L + W] -= 1  # Marking ends at position L+W-1 (effect disappears at L+W)

Complexity

• Time Complexity: \(O(N + K)\)
  • Recording to difference array: \(O(1)\) per marking × \(K\) times = \(O(K)\)
  • Cumulative sum calculation: \(O(N)\)
• Space Complexity: \(O(N)\)
  • Size of difference array and result array

Implementation Notes

1. Be careful with array size: Set the size of diff to \(N+2\). Since \(L + W\) can be at most \(N + 1\), ensure diff[N+1] is accessible.

2. 1-indexed vs 0-indexed: This problem is given in 1-indexed format, so processing with indices starting from 1 is easier to understand.

3. How to compute cumulative sum: Prepare a variable count and add diff[i] sequentially to obtain the number of markings at position \(i\).

Source Code

def solve():
    N, W, K = map(int, input().split())
    
    # Use difference array (imos method)
    diff = [0] * (N + 2)
    
    for _ in range(K):
        L = int(input())
        diff[L] += 1
        diff[L + W] -= 1
    
    # Calculate cumulative sum to get marking counts
    result = []
    count = 0
    for i in range(1, N + 1):
        count += diff[i]
        result.append(count)
    
    print(' '.join(map(str, result)))

solve()

---

This editorial was generated by claude4.5opus.