Overview

Given an initial available time range for a meeting room, we need to find the intersection with sequentially applied usage restrictions, and determine the number of available time slots after each restriction is applied.

Analysis

The essence of the problem is to efficiently compute the intersection of an initial interval \([L, R]\) with sequentially applied intervals \([l_i, r_i]\). The available interval after each restriction is applied can be computed as the intersection of the previous interval and the new restriction interval.

A naive approach would compute the intersection with all restriction intervals each time, taking \(O(i)\) time for the \(i\)-th restriction, resulting in an overall time complexity of \(O(N^2)\). Since \(N\) can be up to \(10^5\), this would not fit within the time limit.

However, since the intersection operation satisfies the associative property, it suffices to maintain only the previous state. In other words, at each step we only need to compute the intersection of the previous interval with the new restriction interval, allowing us to process everything in \(O(N)\).

Algorithm

1. Set the initial interval \([current\_l, current\_r] = [L, R]\)
2. For each restriction \([l_i, r_i]\), perform the following:
   • New left endpoint: \(new\_l = \max(current\_l, l_i)\)
   • New right endpoint: \(new\_r = \min(current\_r, r_i)\)
   • If \(new\_l > new\_r\), the intersection is the empty set (represented as the interval \([1, 0]\))
   • Otherwise, set the interval \([new\_l, new\_r]\) as the new current interval
3. At each step, output the number of elements in the current interval: \(max(0, new\_r - new\_l + 1)\)

With this approach, each restriction is processed in constant time, achieving an overall efficiency of \(O(N)\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (required for storing input data)

Implementation Notes

• When the interval becomes empty (\(new\_l > new\_r\)), all subsequent intersections will also be empty, so we can set the interval to \([1, 0]\) and skip further meaningful computation

• Since input values can be large (up to \(10^9\)), they must be handled accurately with integer arithmetic

• To ensure the number of elements in an empty interval is 0, adjust with \(max(0, count)\)

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    L = int(data[0])
    R = int(data[1])
    N = int(data[2])
    intervals = []
    index = 3
    for i in range(N):
        l = int(data[index])
        r = int(data[index+1])
        index += 2
        intervals.append((l, r))
    
    current_l = L
    current_r = R
    
    for i in range(N):
        l_i, r_i = intervals[i]
        new_l = max(current_l, l_i)
        new_r = min(current_r, r_i)
        if new_l > new_r:
            current_l = 1
            current_r = 0
        else:
            current_l = new_l
            current_r = new_r
        
        count = current_r - current_l + 1
        if count < 0:
            count = 0
        print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.