← 返回题目列表

AtCoder · utpc2012_08

H. 区间排班查询

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

問題

N 职位。 每个工作 i 是开始时间 IL_i 和结束时间 IR_i 已经设置。工作必须从开始时间持续到结束时间进行,一个人不能同时进行多份工作。但是,在前一份工作结束的那个时间点,可以开始下一份工作。也就是说,IR_i = IL_j 的那种工作 i, j 可以连续进行。

Q 人。每个人 k 有可以开始工作的时间 QL_k 和希望工作的结束时间。 QR_k 已经确定。 希望每个人在这段时间内尽可能多地完成工作。 人 k 能够完成工作 i 该值应乘以 QL_k \leq IL_i 和 IR_i \leq QR_k 。 即使多个人完成同一项工作也没关系。 当给出

的工作及人员信息时,请编写一个程序,求出每个人最多可以完成多少项工作。


入力

N Q
IL_1 IR_1
...
IL_N IR_N
QL_1 QR_1
...
QL_Q QR_Q

第一行是工作的数量 N,人员数量 Q 。 是

继续 N 线 i 行提供工作的开始时间 i 时间以整数表示。 IL_i 和结束时间 IR_i 被给予。时间以整数表示。

继续 Q 线 k 行显示人的信息 k 可以开始工作的时间 QL_k 希望结束工作的时间 QR_k 。 是

出力

对每个人,输出表示最多可以进行多少个工作的整数。 换句话说,输出为 Q 由几行组成,k 行显示人的信息 k 输出一个整数,表示最多可以执行多少个工作。

制約

  • 1 \leq N, Q \leq 10^5
  • -10^9 \leq IL_i < IR_i \leq 10^9
  • -10^9 \leq QL_i < QR_i \leq 10^9

部分点

针对该问题的判断设置了一组50分的测试用例。该组中包含的测试用例输入还满足以下条件。

  • 所有查询的正确答案的和不超过 100000。

入力例 1

5 4
0 20
30 40
20 30
10 25
25 40
10 30
0 40
20 40
0 30

输入示例 1 的输出示例

1
3
2
2