CF2052J Judicious Watching

Jill 非常喜欢在大学里取得好成绩，因此她从不拖延作业的截止日期。但她更喜欢和她最好的朋友 Johnny 一起追剧并讨论剧情。不幸的是，今天她需要在这两项活动之间做出选择！ Jill 需要完成 $n$ 个作业任务。第 $i$ 个任务需要 $a_i$ 分钟完成，并且必须在从现在起最多 $d_i$ 分钟内提交给老师。此外，还有 $m$ 集新剧集，Johnny 和 Jill 想要一起讨论。第 $j$ 集剧集时长为 $l_j$ 分钟。Jill 可以以任意顺序完成作业任务，但她必须按照顺序观看剧集。无论是完成作业还是观看剧集，一旦开始都不能中断。 Johnny 和 Jill 需要约定一个时间 $t_k$ 来通话讨论剧集。他们还没确定具体时间。对于每一个可能的时间，请计算 Jill 在该时间之前最多能观看多少集剧集，并且仍然能够按时完成所有 $n$ 个作业任务。 注意，在本题中，假设和 Johnny 的讨论不会占用 Jill 的显著时间，即使 Jill 正在做作业，也可以在 $t_k$ 时刻进行讨论。

输入包含若干组测试数据。第一行为测试组数 $T$（$1 \le T \le 1000$）。 每组测试数据的第一行为三个整数 $n$（$1 \le n \le 200\,000$）——作业任务数，$m$（$1 \le m \le 200\,000$）——剧集数，$q$（$1 \le q \le 200\,000$）——可能的通话时间数。 第二行为 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示完成每个作业所需的时间。下一行为 $n$ 个整数 $d_i$（$1 \le d_i \le 10^{15}$），表示每个作业的截止时间。再下一行为 $m$ 个整数 $l_j$（$1 \le l_j \le 10^9$），表示每集剧集的时长（按观看顺序给出）。最后一行为 $q$ 个整数 $t_k$（$1 \le t_k \le 10^{15}$），表示每个可能的通话时间。 保证所有作业都可以在各自截止时间内完成。 所有测试数据中 $n$、$m$、$q$ 的总和不超过 $200\,000$。

对于每组测试数据，输出一行 $q$ 个整数，依次表示对于每个可能的通话时间 $t_k$，Jill 最多能观看的剧集数。

由 ChatGPT 4.1 翻译