P14129 [SCCPC 2021] True Story

成都双流国际机场是服务于中国四川省省会成都的主要国际机场。2019 年旅客吞吐量达 5590 万人次，成为全球最繁忙的 25 个机场之一，中国大陆第四大机场，以及中国西部最繁忙的机场。 Ema 和她的朋友们即将错过航班。现在在第 $0$ 小时的开始时，他们距离机场还有 $x$ 千米，而登机时间在第 $p_0$ 小时的开始时。共有 $n$ 个人（包括 Ema 自己），第 $i$ 个人的行进速度为 $s_i$ 千米/小时。他们必须不晚于登机时间到达机场，才能赶上飞机。 不过，并非毫无希望。Ema 已经知道登机时间会被多次延期。登机时间会被延期 $k$ 次：第 $i$ 次延期会在第 $t_i$ 小时的开始时宣布，并把登机时间推迟到第 $p_i$ 小时的开始时。不过仍有挑战，因为只有当每个人当前距离登机的时间足够到达机场时，他们才会前进。也就是说，如果从当前时刻到登机时间的剩余时间不足以让某人到达机场，他/她就会停下并待在当前位置；否则，他/她会从停下的地方继续前进，或者一直往前走。 注意，每当登机时间延期时，所有人会立即调整他们的行动。此外，只有当宣布时大家才知道延期，他们无法提前知道并采取行动。 请计算，最终有多少人能够赶上飞机。

每个测试文件只有一组测试数据。 第一行包含四个整数 $n$、$k$、$x$ 和 $p_0$（$1 \leq n, k \leq 10^5$，$1 \leq x, p_0 \leq 10^9$），分别表示人数、延期次数、出发点到机场的距离和初始登机时间。 第二行包含 $n$ 个整数 $s_1, s_2, \cdots, s_n$（$1 \leq s_i \leq 10^9$），表示第 $i$ 个人的速度。 第三行包含 $k$ 个整数 $t_1, t_2, \cdots, t_k$（$1 \leq t_i \leq 10^9$, $t_i < t_{i+1}$, $t_i < p_{i-1}$），表示第 $i$ 次延期通知是在第 $t_i$ 小时宣布。 第四行包含 $k$ 个整数 $p_1, p_2, \cdots, p_k$（$1 \leq p_i \leq 10^9$，$p_i < p_{i+1}$），表示第 $i$ 次通知后登机时间被推迟到第 $p_i$ 小时。

输出一行一个整数，表示最终能赶上飞机的人数。

对于第一个样例，开始时只有速度为 $5$ 的人能赶上机场，他在第 $2$ 小时到达。然后在第 $4$ 小时的时候，速度为 $2$ 的人也可以开始出发，在第 $9$ 小时到达。最终只有这两个人能赶上飞机，其他两个人永远不会踏上征程，因为延期的三次都无法让他们最终按时赶到。 对于第二个样例，唯一的人从头到尾都没有行动。如果他一开始主动出发，可以及时赶到，但他选择了放弃。这个故事告诉我们，并非所有努力都必定成功，但放弃一定会失败。 由 ChatGPT 5 翻译