Overview

This problem requires sequentially computing the intersection of multiple intervals and outputting the number of available time slots after each one. The intersection of intervals can be efficiently computed by simply tracking the maximum of the left endpoints and the minimum of the right endpoints.

Analysis

Key Insight: The Intersection of Intervals is an Interval

The intersection of two closed intervals \([a, b]\) and \([c, d]\) is the interval:

\[[\max(a, c),\ \min(b, d)]\]

If \(\max(a, c) > \min(b, d)\), the intersection is empty.

For example, the intersection of \([2, 10]\) and \([5, 8]\) is \([\max(2,5),\ \min(10,8)] = [5, 8]\), and the number of elements is \(8 - 5 + 1 = 4\).

Comparison with the Naive Approach

A naive approach would enumerate and count all time slots each time a restriction is added, but since \(R - L\) can be up to \(10^9\), processing each time slot individually would result in TLE.

However, since the intersection of intervals can always be represented as a single contiguous interval \([\text{current left endpoint},\ \text{current right endpoint}]\), it is sufficient to maintain just two values: the left and right endpoints.

Incremental Updates

The intersection of \(k\) intervals is:

\[\left[\max(L, l_1, l_2, \ldots, l_k),\ \min(R, r_1, r_2, \ldots, r_k)\right]\]

Each time a new restriction \([l_i, r_i]\) is added, we simply update the left endpoint with \(\max\) and the right endpoint with \(\min\) to obtain the correct intersection.

Algorithm

1. Initialize the current available interval as \([L, R]\).
2. For each restriction \([l_i, r_i]\):
   • Update the left endpoint: \(L \leftarrow \max(L, l_i)\)
   • Update the right endpoint: \(R \leftarrow \min(R, r_i)\)
   • Output the number of available time slots as \(\max(0,\ R - L + 1)\) (if \(L > R\), the interval is empty, so output \(0\))

Concrete Example: Initial interval \([3, 15]\), restrictions are \([5, 12]\), \([1, 8]\)

Step	Restriction	Updated \(L\)	Updated \(R\)	Count
Initial	—	3	15	—
1	\([5, 12]\)	\(\max(3,5)=5\)	\(\min(15,12)=12\)	\(12-5+1=8\)
2	\([1, 8]\)	\(\max(5,1)=5\)	\(\min(12,8)=8\)	\(8-5+1=4\)

Complexity

• Time complexity: \(O(N)\) — \(O(1)\) update and output per restriction
• Space complexity: \(O(1)\) — only two variables, the left endpoint \(L\) and right endpoint \(R\), are maintained

Implementation Notes

• When \(L > R\) (i.e., the intersection becomes empty), it remains empty regardless of any subsequent restrictions. By using max(0, R - L + 1), this case is naturally handled as \(0\).

• Once \(L > R\), \(L\) can only increase and \(R\) can only decrease, so the intersection can never become non-empty again. No special case handling is needed.

  Source Code

L, R = map(int, input().split())
N = int(input())
for _ in range(N):
    l, r = map(int, input().split())
    L = max(L, l)
    R = min(R, r)
    print(max(0, R - L + 1))

---

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