AdditionalFile5672.zip

#5672. 「JOI 2026 Final Day4」面包师

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day4 T1 「パン職人 / Baker」

JOI 面包店以其美味得令人陶醉的羊角面包而闻名。店里共有 $N$ 名面包师，编号为从 $1$ 到 $N$。面包师 $i$ $(1 \leq i \leq N)$ 制作一个羊角面包需要 $i$ 分钟。一名面包师不能同时制作多个羊角面包。

今天，共有 $M$ 名顾客（编号为从 $1$ 到 $M$）预定光顾 JOI 面包店，每位顾客都会订购一个羊角面包。我们将从现在起 $t$ 分钟后的时间称为时刻 $t$。顾客 $j$ $(1 \leq j \leq M)$ 下单的时刻为 $T_j$。如果顾客在下单后 $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$。

第二行包含 $M$ 个整数 $T_1 , T_2 , \cdots , T_M$。

接下来的 $Q$ 行，其中第 $i$ 行包含两个整数 $A_i, B_i$。

输出格式

在标准输出中输出 $Q$ 行。第 $q$ $(1 \leq q \leq Q)$ 行应包含一个整数，表示在第 $q$ 个出勤方案下最多能响应的顾客人数。

样例 1

输入

4 4 6 4
0 2 3 8
2 3
1 6
3 3
4 7

输出

3
2
2
0

对于第 $1$ 个出勤方案，时刻 $3$ 出勤的面包师 $2$ 可以通过例如以下方式响应顾客 $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$。

对于第 $2$ 个出勤方案，时刻 $6$ 出勤的面包师 $1$ 可以通过例如以下方式响应顾客 $2, 3$ 的订单：

• 首先，为了响应顾客 $3$ 的订单，从时刻 $6$ 开始制作一个羊角面包，并在 $1$ 分钟后的时刻 $7$ 完成。（这满足在时刻 $T_3+L=3+6=9$ 之前完成的条件。）
• 接下来，为了响应顾客 $2$ 的订单，从时刻 $7$ 开始制作一个羊角面包，并在 $1$ 分钟后的时刻 $8$ 完成。（这满足在时刻 $T_2+L=2+6=8$ 之前完成的条件。）

顾客 $4$ 的订单是在出勤时刻之后下的，因此会被无视，无法响应。此外，对于必须在时刻 $6$ 之前完成的顾客 $1$ 的订单也无法响应。所以，最多能响应 $2$ 名顾客的订单，第二行输出 $2$。

对于第 $3$ 个出勤方案，时刻 $3$ 出勤的面包师 $3$ 虽然可以响应顾客 $1, 3$ 的订单或顾客 $2, 3$ 的订单，但无法响应顾客 $1, 2, 3$ 的所有订单，同时也无法响应在出勤时刻之后下单的顾客 $4$ 的订单。所以，最多能响应 $2$ 名顾客的订单，第三行输出 $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

输出

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

输出

2
2
4
3
1
2
5
0
3
2

该样例满足子任务 $1, 2, 5, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 4 \times 10^{12}$。
• $1 \leq M \leq 2000000$。
• $1 \leq L \leq 2 \times 10^{12}$。
• $1 \leq Q \leq 400000$。
• $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$	无附加限制