分数: 100 点
问题陈述
JOI Bakery是一家以令人垂涎欲滴的牛角面包而闻名的面包店。 JOI面包店有 N 面包师编号为 1 to N。 贝克 i (1 \leq i \leq N) 需要 i 分钟制作一个牛角面包。 一名面包师无法同时制作多个牛角面包。
今天, M 客户编号为 1 to M 计划去JOI Bakery,每位顾客计划点一份牛角面包。 客户 j (1 \leq j \leq M) 会在某个时间点一份牛角面包 T_j,其中时间 t 表示时间 t 分钟后。 然而,未能在规定时间内收到羊角面包的顾客 L 下单分钟就会放弃并离开店铺。 换句话说,就是为了完成客户的订单 j (1 \leq j \leq M),牛角面包必须按时吃完 T_j + L (包括恰好在时间 T_j + L).
管理 JOI Bakery 的 K 经理计划今天只安排一名面包师工作,并正在考虑派遣哪位面包师以及在什么时间进行工作。 由于面包师在轮班期间主要专注于面包制作, 他们忽略开始时间之后下的所有订单(不包括确切的开始时间)。 也就是说,面包师开始工作的时间 t 无法履行客户的订单 j (1 \leq j \leq M)这样 T_j > t.
K经理目前正在考虑 Q 工作计划。 的 q第计划(1 \leq q \leq Q)是有面包师 A_q 准时开始工作 B_q。 为了帮助做出决定,对于每个 Q 计划,他想知道如果执行该计划,可以履行订单的最大客户数量。 请注意,面包师到达后开始制作羊角面包所需的时间,以及完成一个羊角面包后开始制作新羊角面包所需的时间可以忽略不计。
给定有关访问 JOI Bakery 的客户和工作计划的信息,创建一个程序来查找每个计划可以履行订单的最大客户数量。
输入
从标准输入读取以下数据。
N M L Q T_1 T_2 \cdots T_M A_1 B_1 A_2 B_2 \vdots A_Q B_Q
输出
写 将 Q 行到标准输出。 的 输出的 q- 第行 (1 \leq q \leq Q)应包含一个整数,表示可以在该时间内履行订单的最大客户数 q第工作计划。
约束
- 1 \leq N \leq 4\times 10^{12}.
- 1 \leq M \leq 2\,000\,000.
- 1 \leq L \leq 2\times 10^{12}.
- 1 \leq Q \leq 400\,000.
- 0 \leq T_j \leq 2\times 10^{12} (1 \leq j \leq M).
- T_j \leq T_{j+1} (1 \leq j \leq M-1).
- 1 \leq A_q \leq N (1 \leq q \leq Q).
- 0 \leq B_q \leq 4\times 10^{12} (1 \leq q \leq Q).
- 给定值均为整数。
子任务
- (8 点) M \leq 10, Q \leq 100\,000.
- (12 点) M \leq 500, Q \leq 100\,000.
- (30 点) T_M \leq B_q < T_1+L (1 \leq q \leq Q).
- (10 点) T_M \leq B_q (1 \leq q \leq Q).
- (22 点) M \leq 500\,000, Q \leq 100\,000.
- (18 点)没有额外的限制。
示例输入 1
4 4 6 4 0 2 3 8 2 3 1 6 3 3 4 7
示例输出 1
3 2 2 0
关于第一个工作计划,面包师 2 开始时间 3 可以履行以下订单 3 客户1、2、3为例,如下:
- 首先,为了完成客户1的订单,开始制作牛角面包 3 并在 2 分钟后完成 5。 (这满足按时间完成的条件 T_1 + L = 0 + 6 = 6.)
- 接下来,为了完成顾客2的订单,在某个时间开始制作牛角面包 5 并在 2 分钟后完成 7。 (这满足按时间完成的条件 T_2 + L = 2 + 6 = 8.)
- 最后,为了完成顾客3的订单,在某个时间开始制作牛角面包 7 并在 2 分钟后完成 9。 (这满足按时间完成的条件 T_3 + L = 3 + 6 = 9.)
客户 4 的订单被忽略,因为它在面包师的开始时间之后到达,因此无法履行。因此,最多可以满足 3 个客户的订单,因此第一行输出 3。
关于第二次工作计划,面包师 1 开始时间 6 可以履行2个客户2和3的订单,例如如下:
- 首先,为了完成顾客3的订单,开始制作牛角面包 6 并在 1 分钟后完成 7。 (这满足按时间完成的条件 T_3 + L = 3 + 6 = 9.)
- 接下来,为了完成顾客2的订单,在某个时间开始制作牛角面包 7 并在 1 分钟后完成 8。 (这满足按时间完成的条件 T_2 + L = 2 + 6 = 8.)
客户 4 的订单被忽略,因为它在开始时间之后到达。此外,客户 1 的订单需要在时间 6 之前完成,但无法履行。因此,最多可以满足 2 个客户的订单,因此第 2 行输出 2。
关于第三次工作计划,面包师 3 开始时间 3 可以履行客户 1 和 3、或客户 2 和 3 的订单,但无法履行客户 1、2 和 3 的所有订单。他们也无法履行在开始时间之后到达的客户 4 的订单。因此,最多可以满足 2 个客户的订单,因此第 3 行输出 2。
关于第四次工作计划,贝克 4 开始时间 7 无法履行任何客户的订单。因此,第 4 行输出 0。
此示例输入满足子任务的约束 1,2,5, 和 6.
示例输入 2
20 5 12 4 1 2 4 8 10 1 12 3 10 3 11 15 10
示例输出 2
5 4 3 0
此示例输入满足所有子任务的约束。
示例输入 3
100000 6 272273 10 5 9 209 8128 17202 50102 164 9 11 24 835 9267 2 256 2 314156 18475 142 1826 18978 44757 1 4 1646 218 44
示例输出 3
2 2 4 3 1 2 5 0 3 2
此示例输入满足子任务的约束 1,2,5, 和 6.