Overview

Consider the set of boards that are painted when all painting instructions are executed. From this set, “the portions that were painted only by the \(K\) ignored instructions” are lost.

For each interval, if we know “the set of instruction numbers that paint this portion,” we can efficiently determine for which ignored intervals that portion is lost.

Analysis

First, let \(total\) be the number of boards painted when all instructions are executed.

Let the ignored interval be from the \(s\)-th to the \((s+K-1)\)-th instruction.

A board ends up not being painted only if all instructions that paint it are contained within the ignored interval \([s, s+K-1]\).

That is,

• Let \(A\) be the set of instruction numbers that paint that board
• Let \(mn\) be the minimum of \(A\)
• Let \(mx\) be the maximum of \(A\)

Then, the condition for that board to be lost is:

\[ s \leq mn \]

and

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

The latter can be rearranged to:

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

Therefore, the range of \(s\) for which that board is lost is:

\[ mx - K + 1 \leq s \leq mn \]

However, since \(s\) is the starting position of the ignored interval,

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

must also be satisfied.

---

If we naively compute the union of executed intervals for each \(s\), it would take up to \(O(M^2 \log M)\), which is too slow for \(M \leq 2 \times 10^5\).

Instead, we sweep the board positions from left to right while maintaining “the set of instruction numbers that paint the current position.”

Consecutive portions painted by the same set can be processed together.

For example, suppose a portion of length \(len\) is painted by instruction set \(\{3, 5\}\), and \(K=4\).

For this portion to be lost, the ignored interval must contain both instructions \(3\) and \(5\).

The starting position \(s\) of a consecutive interval of length \(4\) that contains both is:

\[ s \leq 3 \]

and

\[ s+3 \geq 5 \]

so,

\[ 2 \leq s \leq 3 \]

That is, this portion of length \(len\) is lost only when \(s=2,3\).

In this way, each consecutive portion can be added in bulk to the “range of \(s\) where it is lost.”

Algorithm

Treat interval \([L_i, R_i]\) as the half-open interval \([L_i, R_i+1)\).

For each instruction, create the following events:

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

Sort these events by coordinate and sweep from left to right.

During the sweep, maintain the set of instruction numbers currently painting the position using a set called active.

For adjacent event coordinates \(x\) and \(nx\), the contents of active do not change in the interval \([x, nx)\).

The length of this interval is:

\[ len = nx - x \]

If active is non-empty, this portion is painted when all instructions are executed, so:

\[ total += len \]

Also, find the range of ignored starting positions \(s\) for which this portion is lost.

Let \(mn\) be the minimum instruction number in active and \(mx\) be the maximum. The condition for this portion to be lost is:

\[ mx - K + 1 \leq s \leq mn \]

The range of ignored starting position \(s\) is:

\[ 1 \leq s \leq W \]

where

\[ W = M - K + 1 \]

So the actual range to add is:

\[ l = \max(1, mx - K + 1) \]

\[ r = \min(W, mn) \]

If \(l \leq r\), this length \(len\) is lost for \(s=l,l+1,\dots,r\), so we perform a range addition using a difference array.

Finally, reconstruct the number of lost boards lost[s] for each \(s\).

The number of boards ultimately painted is:

\[ total - lost[s] \]

So to maximize this, we need to minimize lost[s].

The answer is:

\[ total - \min_s lost[s] \]

Complexity

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

The number of events is \(2M\).

Sorting events takes \(O(M \log M)\), and insertions/deletions to the set during the sweep each take \(O(\log M)\), so the overall complexity is \(O(M \log M)\).

Implementation Notes

Since interval \([L_i, R_i]\) includes both endpoints, we use \(R_i+1\) in the events to treat it as the half-open interval \([L_i, R_i+1)\).

This way, the length \(nx-x\) between adjacent event coordinates \(x\) and \(nx\) directly corresponds to the number of painted boards.

Also, when multiple events occur at the same coordinate, all of them must be processed before considering the interval to the next coordinate.

Since we want to retrieve the minimum and maximum instruction numbers currently painting from active, using a set allows us to obtain them as:

int mn = *active.begin();
int mx = *active.rbegin();

Since the number of boards \(N\) can be up to \(10^9\), coordinates and answers should be handled with long long type.

Source Code

#include <bits/stdc++.h>
using namespace std;

struct Event {
    long long x;
    int id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    int M, K;
    cin >> N >> M >> K;

    vector<Event> events;
    events.reserve(2 * M);

    for (int i = 1; i <= M; i++) {
        long long L, R;
        cin >> L >> R;
        events.push_back({L, i});
        events.push_back({R + 1, -i});
    }

    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        return a.x < b.x;
    });

    int W = M - K + 1;
    vector<long long> diff(W + 3, 0);

    set<int> active;
    long long total = 0;

    size_t p = 0;
    while (p < events.size()) {
        long long x = events[p].x;

        while (p < events.size() && events[p].x == x) {
            int id = events[p].id;
            if (id > 0) active.insert(id);
            else active.erase(-id);
            p++;
        }

        if (p == events.size()) break;

        long long nx = events[p].x;
        long long len = nx - x;

        if (len > 0 && !active.empty()) {
            total += len;

            int mn = *active.begin();
            int mx = *active.rbegin();

            int l = max(1, mx - K + 1);
            int r = min(W, mn);

            if (l <= r) {
                diff[l] += len;
                diff[r + 1] -= len;
            }
        }
    }

    long long cur = 0;
    long long min_lost = LLONG_MAX;

    for (int s = 1; s <= W; s++) {
        cur += diff[s];
        min_lost = min(min_lost, cur);
    }

    cout << total - min_lost << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.