← 返回题目列表

Codeforces · 816/B

B. 凯伦和咖啡

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

为了在课堂上保持清醒和专心,凯伦需要一些咖啡!

咖啡爱好者凯伦想知道冲泡一杯完美咖啡的最佳温度。事实上,她花了一些时间阅读了几本食谱书籍,包括广受好评的《The Art of the Covfefe》。

她知道 n 个咖啡食谱。第 i 个配方建议咖啡应该在 li 和 ri 度(含)之间冲泡,以获得最佳口味。

Karen 认为,如果至少有 k 个食谱推荐某个温度,则该温度是可接受的。

凯伦的头脑相当善变,所以她问了q个问题。在每个问题中,假设她只想准备温度介于 a 和 b 之间(含)的咖啡,您能否告诉她有多少个允许的整数温度落在该范围内?

输入

输入的第一行包含三个整数,n、k (1 ≤ k ≤ n ≤ 200000) 和 q (1 ≤ q ≤ 200000)、食谱数量、一定温度下必须推荐的最少食谱数量以及 Karen 的问题数量。

接下来的 n 行描述了食谱。具体来说,其中的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ 200000),描述第 i 个配方建议在 li 和 ri 度之间(包括 li 和 ri 度)冲泡咖啡。

接下来的 q 行描述了问题。这些行中的每一行都包含 a 和 b,(1 ≤ a ≤ b ≤ 200000),描述她想知道 a 和 b 度(含)之间的允许整数温度的数量。

输出

对于每个问题,在一行中单独输出一个整数,即 a 度和 b 度(含)之间允许的整数温度的数量。

示例

输入 #1

3 2 4
91 94
92 97
97 99
92 94
93 97
95 96
90 100

输出 #1

3
3
0
4

输入 #2

2 1 1
1 1
200000 200000
90 100

输出 #2

0

注意

在第一个测试用例中,Karen 知道 3 个食谱。

1. 第一个建议在 91 至 94 度(含)之间冲泡咖啡。
2. 第二个建议在 92 至 97 度(含)之间冲泡咖啡。
3. 第三个建议在 97 度到 99 度(含)之间冲泡咖啡。

如果至少有 2 个食谱推荐某个温度,则该温度是可接受的。

她问了 4 个问题。

在第一个问题中,她想知道 92 到 94 度(含)之间允许的整数温度的数量。有3种:92度、93度、94度都可以。

在第二个问题中,她想知道 93 到 97 度(含)之间允许的整数温度的数量。有3种:93度、94度、97度都可以。

在第三个问题中,她想知道 95 到 96 度(含)之间允许的整数温度的数量。没有。

在她的最后一个问题中,她想知道 90 到 100 度(含)之间允许的整数温度的数量。有4种:92度、93度、94度、97度都可以。

在第二个测试用例中,Karen 知道 2 个食谱。

1. 第一个,“wikiHow to make Cold Brew Coffee”,建议在正好 1 度的温度下冲泡咖啡。
2. 第二个,“咖啡不是在太阳表面温度至少 36.3306 倍的温度下冲泡的,有什么好处?”,建议在 200000 度的温度下冲泡咖啡。

如果至少有 1 个配方推荐某个温度,则该温度是可接受的。

在她的第一个问题也是唯一的问题中,她想知道实际上合理的允许整数温度的数量。没有。