← 返回题目列表

AtCoder · ndpc2026_e

E. 暑假

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

分数: 3 点

问题陈述

你的暑假从今天开始,持续时间 N 天。
有 M 事件。 i第一个活动于当天早上开始 A_i 并于当天晚上结束 B_i.

你被给予 Q 查询。在每个查询中,您都会得到两个整数 L 和 R,您需要回答以下问题:

您决定从当天起参加尽可能多的活动 L 到今天 R.
但是,您无法中途加入或离开活动。因此,您不能参加多个时间段重叠的活动,也不能参加当天之前开始的活动 L 或当天后结束 R.
如果您选择最佳的活动,您最多可以参加多少场活动?

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq B_i \leq N
  • 1 \leq L \leq R \leq N
  • 所有输入值均为整数

输入

输入由标准输入给出,格式如下:

N M Q
A_1 B_1
A_2 B_2
\vdots
A_M B_M
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均按以下格式给出:

L R

输出

打印 Q 行。对于 i第行,输出答案 i第一个查询。


示例输入 1

5 3 3
1 3
4 5
2 2
1 5
1 1
3 5

示例输出 1

2
0
1

例如,在第一个查询中,您可以参加第 1 个和第 2 个活动,这是最多的。


示例输入 2

9 13 8
4 6
1 5
8 9
5 6
1 7
4 9
4 6
2 8
5 6
5 8
2 6
3 7
1 3
5 7
5 7
5 7
3 4
1 8
2 6
6 8
8 9

示例输出 2

1
1
1
0
2
1
0
1