Overview

Given an initial interval \([L, R]\), we sequentially apply restriction intervals \([l_i, r_i]\) by taking intersections, and for each step we need to find the number of integer time points remaining (the length of the interval).

Analysis

No matter how many times we repeat the intersection operation, the result is always “a single interval.” This is because the intersection of two intervals (if non-empty) is again an interval.

Let \([curL, curR]\) be the resulting interval after applying the first \(k\) restrictions. Then, after applying the next restriction \([l, r]\):

• The left endpoint moves further right: \(curL \leftarrow \max(curL, l)\)
• The right endpoint moves further left: \(curR \leftarrow \min(curR, r)\)

This is all we need to update.

A naive approach such as “maintaining all available time points (integers) and removing them one by one” would be infeasible since \(R-L\) can be up to \(10^9\), causing both time and memory to blow up. By managing the interval using only its endpoints (two integers), we can process each query in \(O(1)\).

The condition for the intersection being empty is \(curL > curR\), in which case the count is \(0\). When it is non-empty, the number of integers includes both endpoints, so it is \(curR - curL + 1\).

Example: - Initial \([L,R]=[2,10]\) - Restriction 1 \([4,8]\) → \([4,8]\), count \(8-4+1=5\) - Restriction 2 \([7,12]\) → \(\max(4,7)=7,\ \min(8,12)=8\), so \([7,8]\), count \(2\) - Restriction 3 \([9,9]\) → \([9,8]\), which is empty, count \(0\)

Algorithm

1. Initialize the current intersection interval as \(curL=L,\ curR=R\).
2. For each restriction \([l_i, r_i]\) in order:
   • \(curL \leftarrow \max(curL, l_i)\)
   • \(curR \leftarrow \min(curR, r_i)\)
   • If \(curL \le curR\), output \(curR-curL+1\); otherwise, output \(0\).

Complexity

• Time complexity: \(O(N)\) (each restriction is processed in constant time)
• Space complexity: \(O(1)\) (excluding output)

Implementation Notes

• Note that the count is \(curR-curL+1\) because both endpoints are included.

• Once \(curL > curR\), the set is empty so output \(0\) (you may continue updating afterwards).

• Since the input can be large, in Python it is safer to use fast input methods such as sys.stdin.buffer.read().

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    L = int(next(it))
    R = int(next(it))
    N = int(next(it))

    out = []
    curL, curR = L, R
    for _ in range(N):
        l = int(next(it))
        r = int(next(it))
        if l > curL:
            curL = l
        if r < curR:
            curR = r
        if curL <= curR:
            out.append(str(curR - curL + 1))
        else:
            out.append("0")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.