Overview

Given an initial available time interval and multiple usage restrictions, find the length of the available time interval after each restriction is added.

Analysis

In this problem, we apply \(N\) interval restrictions \([l_i, r_i]\) in order to the initial interval \([L, R]\). Each interval restriction corresponds to taking the intersection of the current available time interval with that restriction interval.

That is, if the current available interval is \([current\_L, current\_R]\), then when a new restriction \([l_i, r_i]\) arrives, the effective interval becomes: $\( [current\_L, current\_R] \cap [l_i, r_i] = [\max(current\_L, l_i), \min(current\_R, r_i)] \)$

If \(\max(current\_L, l_i) > \min(current\_R, r_i)\), the intersection is empty, so the available time becomes 0.

A naive approach would be to recompute the intersection considering all restrictions each time, but this takes \(O(N)\) per step, resulting in \(O(N^2)\) overall, which is too slow (since \(N\) can be up to \(10^5\)). However, since “restrictions that have already been applied are always considered going forward,” it is sufficient to incrementally update the current effective interval.

Algorithm

1. Start by maintaining the available interval \([L, R]\).
2. For each restriction \([l_i, r_i]\), perform the following:
   • Compute the intersection of the current interval \([current\_L, current\_R]\) and \([l_i, r_i]\): $\( new\_L = \max(current\_L, l_i), \quad new\_R = \min(current\_R, r_i) \)$
   • If \(new\_L > new\_R\), the intersection is empty, so the answer is 0.
   • Otherwise, the length of the interval \(new\_R - new\_L + 1\) is the answer.
   • Save the new interval for the next step.

In this way, each restriction can be processed in constant time, and the overall solution runs in \(O(N)\).

Example

Initial interval: \([10, 30]\) Restrictions: 1. \([15, 25]\) → Intersection: \([15, 25]\) → Length: 11 2. \([20, 40]\) → Intersection: \([20, 25]\) → Length: 6 3. \([5, 18]\) → Intersection: \([20, 18]\) → Empty set → Length: 0

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• sys.stdin.read is used for fast input reading.

• Once the interval becomes empty, it stays 0 from that point on, so it is safe to explicitly set the state to something like \([0, -1]\).

• Computing the intersection of intervals can be easily done using just max and min.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    L = int(data[0])
    R = int(data[1])
    N = int(data[2])
    
    current_L = L
    current_R = R
    results = []
    
    index = 3
    for _ in range(N):
        l = int(data[index])
        r = int(data[index + 1])
        index += 2
        
        # 区間の共通部分を計算
        current_L = max(current_L, l)
        current_R = min(current_R, r)
        
        # 空集合かどうかを判定
        if current_L > current_R:
            current_L = 0
            current_R = -1
            results.append(0)
        else:
            results.append(current_R - current_L + 1)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.