Overview

This is a problem about sequentially computing the intersection of intervals. Each time a new restriction is added, we update the left and right endpoints of the available interval and output the number of integers contained within that range.

Analysis

As a naive approach, if we try to directly manage the available time slots using an array or set, the maximum time value is \(10^9\), which is extremely large, causing Memory Limit Exceeded (MLE) or Time Limit Exceeded (TLE).

Here, we focus on the property that “the intersection of two intervals is also a single interval.” If the current available interval is \([L, R]\) and a new restriction is \([l_i, r_i]\), then the interval satisfying both conditions is \([\max(L, l_i), \min(R, r_i)]\).

Let’s consider a concrete example. If the current interval is \([2, 8]\) and the new restriction is \([5, 10]\), the intersection is \([\max(2, 5), \min(8, 10)] = [5, 8]\).

In this way, by maintaining the current left endpoint \(L\) and right endpoint \(R\) as variables and updating them each time we receive input, we can efficiently compute the answer. Note that if the restrictions become too tight and \(L > R\) after an update, the intersection is empty (the empty set), so the number of available time slots is \(0\).

Algorithm

1. Set the variables \(L\) and \(R\), representing the current available interval, to their initial values.
2. For each of the \(N\) restrictions, perform the following operations in order:
   • Read the left endpoint \(l_i\) and right endpoint \(r_i\) of the new restriction.
   • Update the left endpoint \(L\) to \(\max(L, l_i)\) (equivalent to if l > L: L = l in code).
   • Update the right endpoint \(R\) to \(\min(R, r_i)\) (equivalent to if r < R: R = r in code).
   • Compute the number of available time slots \(count = R - L + 1\).
   • If \(count < 0\), the intersection does not exist, so set \(count = 0\).
   • Record \(count\) as the answer.
3. Output the recorded answers.

Complexity

• Time complexity: \(O(N)\) The update operation for each restriction (computing \(\max\) and \(\min\)) takes \(O(1)\). Since this is repeated \(N\) times, the overall time complexity is \(O(N)\).
• Space complexity: \(O(N)\) We use \(O(N)\) memory for the list to read all input at once and the list to store the output results.

Implementation Notes

• Speeding up I/O: In Python, repeatedly calling input() or print() tens of thousands of times can result in Time Limit Exceeded (TLE). Therefore, we read all input at once using sys.stdin.read().split(), and accumulate the output in a list before printing it all at once with '\n'.join().

• Empty set detection: When \(L\) and \(R\) are inverted and \(R - L + 1\) becomes negative, care must be taken not to output that value directly. In the code, this is handled appropriately with if count < 0: count = 0.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    L = int(input_data[0])
    R = int(input_data[1])
    N = int(input_data[2])
    
    ans = []
    idx = 3
    for _ in range(N):
        l = int(input_data[idx])
        r = int(input_data[idx+1])
        idx += 2
        
        if l > L:
            L = l
        if r < R:
            R = r
            
        count = R - L + 1
        if count < 0:
            count = 0
        ans.append(str(count))
        
    sys.stdout.write('\n'.join(ans) + '\n')

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.