CF1611F ATM and Students

Polycarp 开始在银行工作。他被分配去监控 ATM 机。ATM 机初始时有 $s$ 卢布。 有 $n$ 个学生排成一队。每个学生要么想取出一定金额的钱，要么想向账户存入一定金额。如果 $a_i$ 是正数，则该学生通过 ATM 存入该金额；如果 $a_i$ 是负数，则该学生取出 $|a_i|$ 卢布。 一开始，ATM 机是关闭的，有任意数量的学生未被服务。在某一时刻，Polycarp 打开 ATM 机，ATM 机中有初始的 $s$ 卢布。然后，剩下的学生开始依次在 ATM 机前排队。如果在某一时刻，ATM 机中的钱少于某个学生想要取出的金额，则该学生无法被服务，Polycarp 关闭 ATM 机，并且不再打开。 更正式地说，被服务的学生形成一个连续的子序列。 Polycarp 希望 ATM 能服务最多数量的学生。请帮助他。输出第一个和最后一个被服务学生的编号，或者判断他无法服务任何学生。 换句话说，找到这样一个最长的连续学生区间，使得从 ATM 机初始有 $s$ 卢布开始，所有这些学生都能被服务。ATM 机依次为学生服务（即按照队列顺序）。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含两行。第一行包含整数 $n$ 和 $s$（$1 \le n \le 2\cdot10^5$，$0 \le s \le 10^9$），表示数组 $a$ 的长度和 ATM 机的初始卢布数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$），表示数组 $a$ 的元素。注意 $a_i$ 可能为零。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出 $t$ 行，每行对应一个测试用例的答案：如果存在答案，输出第一个和最后一个被服务学生的编号。如果没有解，输出 $-1$。 如果有多种可能的答案，输出任意一种即可。

在第一个测试用例中，唯一正确答案是 $2\ 4$，因为服务这些学生时，ATM 机中的卢布数不会变为负数，并且这是可以服务的最大学生数量。 在第二个测试用例中，答案是 $-1$，因为 ATM 机的钱对任何一个学生来说都不够。 在第三个测试用例中，答案可以是 $1\ 2$ 或 $4\ 5$。 由 ChatGPT 4.1 翻译