問題
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