/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は会社の会議室を予約しようとしています。会議室の利用可能な時間帯は、はじめ、整数 L 以上 R 以下の各時刻、すなわち時刻 L, L+1, \ldots, R の R - L + 1 個です。
高橋君が予約システムの履歴を確認したところ、N 件の利用制限が順番に登録されていることがわかりました。i 番目の利用制限は「会議室を利用できるのは時刻 l_i 以上 r_i 以下のみに制限する」というものです。
利用制限が登録されるたびに、実際に利用可能な時刻の集合は、それまでの利用可能な時刻の集合と新たな制限の共通部分に更新されます。すなわち、k 番目の利用制限までが登録された時点で利用可能な時刻の個数は、整数の集合
[L, R] \cap [l_1, r_1] \cap [l_2, r_2] \cap \cdots \cap [l_k, r_k]
の要素数です。ここで [a, b] は a 以上 b 以下の整数全体の集合を表します。この共通部分が空集合である場合、利用可能な時刻の個数は 0 です。
i = 1, 2, \ldots, N のそれぞれについて、i 番目の利用制限が登録された直後の利用可能な時刻の個数を求めてください。
制約
- 0 \leq L \leq R \leq 10^9
- 1 \leq N \leq 10^5
- 0 \leq l_i \leq r_i \leq 10^9
- 入力はすべて整数である
入力
L R N l_1 r_1 l_2 r_2 \vdots l_N r_N
- 1 行目には、初期の利用可能範囲の左端 L と右端 R が、スペース区切りで与えられる。
- 2 行目には、利用制限の個数 N が与えられる。
- 続く N 行のうち i 行目には、i 番目の利用制限の左端 l_i と右端 r_i が、スペース区切りで与えられる。
出力
N 行出力せよ。i 行目には、i 番目の利用制限が登録された直後の利用可能な時刻の個数を出力せよ。
入力例 1
1 10 3 3 8 4 6 2 5
出力例 1
6 3 2
入力例 2
0 5 4 1 4 2 3 5 5 0 2
出力例 2
4 2 0 0
入力例 3
10 30 8 8 25 12 28 15 22 14 20 18 18 0 100 19 30 17 17
出力例 3
16 14 8 6 1 1 0 0
入力例 4
123456789 987654321 12 100000000 900000000 200000000 950000000 300000000 800000000 250000000 850000000 400000000 750000000 450000000 700000000 500000000 680000000 550000000 600000000 560000000 590000000 570000000 580000000 575000000 576000000 576000001 576000010
出力例 4
776543212 700000001 500000001 500000001 350000001 250000001 180000001 50000001 30000001 10000001 1000001 0
入力例 5
0 0 1 0 0
出力例 5
1
Score : 300 pts
Problem Statement
Takahashi is trying to reserve a meeting room at his company. The available time slots for the meeting room are initially all integer times from L to R inclusive, namely the R - L + 1 times L, L+1, \ldots, R.
When Takahashi checked the reservation system's history, he found that N usage restrictions had been registered in order. The i-th usage restriction is: "The meeting room can only be used at times from l_i to r_i inclusive."
Each time a usage restriction is registered, the set of actually available times is updated to the intersection of the previously available set of times and the new restriction. In other words, the number of available times after the first k usage restrictions have been registered is the number of elements in the set of integers
[L, R] \cap [l_1, r_1] \cap [l_2, r_2] \cap \cdots \cap [l_k, r_k]
where [a, b] denotes the set of all integers from a to b inclusive. If this intersection is empty, the number of available times is 0.
For each i = 1, 2, \ldots, N, find the number of available times immediately after the i-th usage restriction is registered.
Constraints
- 0 \leq L \leq R \leq 10^9
- 1 \leq N \leq 10^5
- 0 \leq l_i \leq r_i \leq 10^9
- All input values are integers.
Input
L R N l_1 r_1 l_2 r_2 \vdots l_N r_N
- The first line contains the left endpoint L and right endpoint R of the initial available range, separated by a space.
- The second line contains the number of usage restrictions N.
- The i-th of the following N lines contains the left endpoint l_i and right endpoint r_i of the i-th usage restriction, separated by a space.
Output
Print N lines. The i-th line should contain the number of available times immediately after the i-th usage restriction is registered.
Sample Input 1
1 10 3 3 8 4 6 2 5
Sample Output 1
6 3 2
Sample Input 2
0 5 4 1 4 2 3 5 5 0 2
Sample Output 2
4 2 0 0
Sample Input 3
10 30 8 8 25 12 28 15 22 14 20 18 18 0 100 19 30 17 17
Sample Output 3
16 14 8 6 1 1 0 0
Sample Input 4
123456789 987654321 12 100000000 900000000 200000000 950000000 300000000 800000000 250000000 850000000 400000000 750000000 450000000 700000000 500000000 680000000 550000000 600000000 560000000 590000000 570000000 580000000 575000000 576000000 576000001 576000010
Sample Output 4
776543212 700000001 500000001 500000001 350000001 250000001 180000001 50000001 30000001 10000001 1000001 0
Sample Input 5
0 0 1 0 0
Sample Output 5
1