Overview

We consider subtracting “the number of boards that become unpainted due to ignoring” from the number of boards that would be painted if all painting instructions were executed.
For each board, it is lost only when the set of instruction numbers that paint that board is entirely contained within the \(K\) consecutive instructions that are ignored.

Analysis

Let \(S_x\) be the set of instruction numbers that paint board \(x\).

When the ignored interval is \([s, s+K-1]\), board \(x\) ends up unpainted in the following case:

• It was originally painted at least once
• All instructions that paint that board are contained in the ignored interval \([s, s+K-1]\)

That is, board \(x\) is “lost” only when:

\[ S_x \subseteq [s, s+K-1] \]

Therefore, the answer is:

\[ \text{Number of boards painted when all instructions are executed} - \text{Minimum number of lost boards} \]

---

If we naively collect the executed instructions for each \(s\) and compute the union of intervals, there are up to \(M\) possible values of \(s\), and each takes \(O(M \log M)\), resulting in \(O(M^2 \log M)\) overall, which is too slow.

Also, since \(N\) can be up to \(10^9\), we cannot examine each board individually.

Therefore, we focus only on the endpoints of the painting intervals.
Between the endpoints of intervals, “the set of instructions currently painting that location” does not change.

For example, suppose the active instruction set for a consecutive range of boards is:

\[ S = \{2, 5, 6\} \]

For this range to be lost, the ignored interval \([s, s+K-1]\) must contain all of \(2, 5, 6\).
That is, it suffices to look only at the minimum and maximum instruction numbers.

\[ \min S = 2,\quad \max S = 6 \]

So the condition is:

\[ s \leq 2 \]

and

\[ s+K-1 \geq 6 \]

Rearranging:

\[ 6-K+1 \leq s \leq 2 \]

In general, if the current active instruction set is \(S\), with minimum \(\mathrm{mn}\) and maximum \(\mathrm{mx}\), then the values of \(s\) for which this range is lost satisfy:

\[ \mathrm{mx}-K+1 \leq s \leq \mathrm{mn} \]

However, since \(s\) must satisfy:

\[ 1 \leq s \leq M-K+1 \]

the actual range is:

\[ \max(1, \mathrm{mx}-K+1) \leq s \leq \min(\mathrm{mn}, M-K+1) \]

For all \(s\) in this range, we add “the length of this board range” to the number of lost boards.

Algorithm

First, we treat each painting instruction \([L_i, R_i]\) as a half-open interval:

\[ [L_i, R_i+1) \]

This way, the length can be directly expressed as:

\[ R_i+1-L_i \]

For each instruction, we create the following 2 types of events:

• At position \(L_i\), instruction \(i\) becomes active
• At position \(R_i+1\), instruction \(i\) becomes inactive

We process these events in order of coordinate.

---

During the sweep, for the currently active instruction number set \(S\), we want to efficiently obtain:

• The minimum instruction number \(\mathrm{mn}\)
• The maximum instruction number \(\mathrm{mx}\)

For this, we use two heaps:

• A min-heap for obtaining the minimum
• A max-heap for obtaining the maximum

In Python, since there is no max-heap, we manage it by inserting negated values.

For deletion, since it is difficult to directly remove from a heap, we manage whether instruction \(i\) is currently active with alive[i], and perform lazy deletion by removing the top of the heap if it is an inactive instruction.

---

After processing all events at coordinate \(x\), let \(nx\) be the next event coordinate.

At this point, in the interval:

\[ [x, nx) \]

the active instruction set does not change.

The length is:

\[ nx-x \]

If there is at least one active instruction, this range would be painted when all instructions are executed, so we add the length to total.

Furthermore, we find the starting position \(s\) of the ignored interval for which this range is lost.

If the minimum of the currently active instruction numbers is \(\mathrm{mn}\) and the maximum is \(\mathrm{mx}\), the condition for this range to be lost is:

\[ [s, s+K-1] \supseteq [\mathrm{mn}, \mathrm{mx}] \]

Therefore:

\[ \mathrm{mx}-K+1 \leq s \leq \mathrm{mn} \]

The actually selectable \(s\) satisfies:

\[ 1 \leq s \leq M-K+1 \]

So the range to add to is from:

\[ \max(1, \mathrm{mx}-K+1) \]

to:

\[ \min(\mathrm{mn}, M-K+1) \]

We add the current length to this range.

To perform range addition efficiently, we use the imos method (difference array technique).
By setting diff[l] += length, diff[r+1] -= length, and taking the prefix sum at the end, we can determine the number of lost boards for each \(s\).

Finally, letting the minimum number of lost boards be min_loss:

\[ \text{answer} = \text{total} - \text{min\_loss} \]

is output.

Complexity

• Time complexity: \(O(M \log M)\)
• Space complexity: \(O(M)\)

The number of events is 2 per instruction, so \(2M\) events in total.
Sorting the events takes \(O(M \log M)\), and heap operations during the sweep also take \(O(M \log M)\) overall.

Implementation Details

By treating intervals as half-open \([L_i, R_i+1)\), the number of consecutive boards can be simply computed as the coordinate difference.

events[p] = (l << shift) | i
events[p] = ((r + 1) << shift) | (M + i)

In the code, events are packed into integers rather than tuples.
This is for optimization purposes, and semantically it is the same as having the following events:

• (coordinate, instruction number) : addition event
• (coordinate, M + instruction number) : deletion event

Also, all events at the same coordinate are processed together.
After that, for the interval up to the next event coordinate, we process it assuming the active instruction set is constant.

Since deleted instructions may remain in the heap, we remove them if the top is inactive.

while min_heap and not alive[min_heap[0]]:
    heappop(min_heap)

while max_heap and not alive[-max_heap[0]]:
    heappop(max_heap)

This allows us to correctly obtain the minimum and maximum of the currently active instruction numbers.

Source Code

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())

    shift = (2 * M + 1).bit_length()
    mask = (1 << shift) - 1

    events = [0] * (2 * M)
    p = 0
    for i in range(1, M + 1):
        l, r = map(int, input().split())
        events[p] = (l << shift) | i
        p += 1
        events[p] = ((r + 1) << shift) | (M + i)
        p += 1

    events.sort()

    s_count = M - K + 1
    diff = [0] * (s_count + 2)

    alive = bytearray(M + 1)
    min_heap = []
    max_heap = []
    heappush = heapq.heappush
    heappop = heapq.heappop

    total = 0
    i = 0
    e_len = 2 * M

    while i < e_len:
        x = events[i] >> shift

        while i < e_len and (events[i] >> shift) == x:
            code = events[i] & mask
            if code <= M:
                idx = code
                alive[idx] = 1
                heappush(min_heap, idx)
                heappush(max_heap, -idx)
            else:
                idx = code - M
                alive[idx] = 0
            i += 1

        while min_heap and not alive[min_heap[0]]:
            heappop(min_heap)
        while max_heap and not alive[-max_heap[0]]:
            heappop(max_heap)

        if i < e_len and min_heap:
            length = (events[i] >> shift) - x
            total += length

            mn = min_heap[0]
            mx = -max_heap[0]

            if mx - mn < K:
                left = mx - K + 1
                if left < 1:
                    left = 1
                right = mn
                if right > s_count:
                    right = s_count

                if left <= right:
                    diff[left] += length
                    diff[right + 1] -= length

    cur = 0
    min_loss = 10**30
    for s in range(1, s_count + 1):
        cur += diff[s]
        if cur < min_loss:
            min_loss = cur

    print(total - min_loss)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.