P15948 [JOI Final 2026] 面包师 / Baker

JOI 面包店是一家以令人垂涎的牛角面包而闻名的面包店。JOI 面包店有 $N$ 名面包师，编号从 $1$ 到 $N$。面包师 $i$ ($1 \leq i \leq N$) 制作一个牛角面包需要 $i$ 分钟。一名面包师不能同时制作多个牛角面包。 今天，有 $M$ 名编号从 $1$ 到 $M$ 的顾客计划光顾 JOI 面包店，每位顾客都计划订购一个牛角面包。顾客 $j$ ($1 \leq j \leq M$) 将在时间 $T_j$ 订购一个牛角面包，其中时间 $t$ 表示从现在起 $t$ 分钟后的时间。然而，如果顾客在下单后 $L$ 分钟内无法收到他们的牛角面包，他们就会放弃并离开商店。换句话说，为了完成顾客 $j$ ($1 \leq j \leq M$) 的订单，牛角面包必须在时间 $T_j + L$ 之前（包括恰好在时间 $T_j + L$）制作完成。 管理 JOI 面包店的经理 K 计划今天只让一名面包师工作，并且正在考虑派遣哪位面包师以及在什么时间开始工作。由于面包师在值班期间会高度专注地制作面包，**他们会忽略所有在他们开始时间之后（不包括恰好在开始时间）下的订单**。也就是说，在时间 $t$ 开始工作的面包师无法完成满足 $T_j > t$ 的顾客 $j$ ($1 \leq j \leq M$) 的订单。 经理 K 目前正在考虑 $Q$ 个工作计划。第 $q$ 个计划 ($1 \leq q \leq Q$) 是让面包师 $A_q$ 在时间 $B_q$ 开始工作。为了帮助做出决定，对于这 $Q$ 个计划中的每一个，他想知道如果执行该计划，可以完成的订单的最大顾客数量。请注意，面包师到达后开始制作牛角面包所需的时间，以及制作完一个后开始制作下一个新牛角面包所需的时间，均可以忽略不计。 给定有关光顾 JOI 面包店的顾客信息和工作计划，编写一个程序，求出每个计划中可以完成订单的最大顾客数量。

从标准输入读取以下数据。 > $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 关于第 $1$ 个工作计划，面包师 $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$ 位顾客的订单，所以第 $1$ 行输出 $3$。 关于第 $2$ 个工作计划，面包师 $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$ 在时间 $3$ 开始工作，可以完成顾客 $1$ 和 $3$、或者顾客 $2$ 和 $3$ 的订单，但不能同时完成顾客 $1, 2$ 和 $3$ 的所有订单。他们也无法完成在开始时间之后到达的顾客 $4$ 的订单。因此，最多可以完成 $2$ 位顾客的订单，所以第 $3$ 行输出 $2$。 关于第 $4$ 个工作计划，面包师 $4$ 在时间 $7$ 开始工作，无法完成任何顾客的订单。因此，第 $4$ 行输出 $0$。 该样例输入满足子任务 $1, 2, 5$ 和 $6$ 的约束。 ### 样例 2 该样例输入满足所有子任务的约束。 ### 样例 3 该样例输入满足子任务 $1, 2, 5$ 和 $6$ 的约束。 ### 约束条件 - $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$)。 - 给定的值均为整数。 ### 子任务 1. (8 分) $M \leq 10, Q \leq 100000$。 2. (12 分) $M \leq 500, Q \leq 100000$。 3. (30 分) $T_M \leq B_q < T_1 + L$ ($1 \leq q \leq Q$)。 4. (10 分) $T_M \leq B_q$ ($1 \leq q \leq Q$)。 5. (22 分) $M \leq 500000, Q \leq 100000$。 6. (18 分) 无附加约束。