分数: 300 分
问题陈述
高桥正在尝试在他的公司预订会议室。会议室的可用时隙最初都是从 L to R 包括在内,即 R - L + 1 次 L, L+1, \ldots, R.
高桥查看预订系统的历史记录时发现, N 使用限制已按顺序注册。的 i-th 使用限制是:“会议室只能在以下时间使用: l_i to 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 to 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
- 第一行包含左端点 L 和右端点 初始可用范围的 R ,以空格分隔。
- 第二行包含使用次数限制 N.
- 的 i- 以下各项 N 行包含左端点 l_i 和右端点 初始可用范围的 r_i 的 i-th 使用限制,以空格分隔。
输出
打印 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