← 返回题目列表

AtCoder · awc0037_b

B. 会议室的可用时间段

中文机器翻译题面 查看原题

分数: 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