CF164E Polycarpus and Tasks

Polycarpus 要处理很多任务。每个任务由三个整数 $l_i$、$r_i$ 和 $t_i$ 表示。表示任务 $i$ 时，必须选择一个整数 $s_i$，使得 $l_i \le s_i$ 且 $s_i + t_i - 1 \le r_i$，然后从时间 $s_i$ 开始连续执行任务 $t_i$ 个时间单位，直到时间 $s_i + t_i - 1$。也就是说，一个任务需要在开始时间不早于 $l_i$ 且结束时间不晚于 $r_i$ 的前提下，连续执行 $t_i$ 个单位时间。 Polycarpus 的任务有个奇妙的性质：对于任何两个任务 $j$ 和 $k$，若 $j < k$，则有 $l_j < l_k$ 且 $r_j < r_k$。 有一个有序的任务集合 $A$，其中包含 $|A|$ 个任务。我们定义 $a_j = (l_j, r_j, t_j)$（$1 \le j \le |A|$），并假设这些任务是按 $l_j$ 的递增顺序排列的。 我们定义一个递归函数 $f$，其参数为一个任务集合 $A$，结果是一个整数。函数 $f(A)$ 采用如下的贪心算法，用伪代码描述如下： 1. 初始化 $ans = 0$。 2. 按照任务编号的递增顺序依次考虑集合 $A$ 中的所有任务，设当前任务的计数器 $i = 0$。 3. 处理下一个任务：$i = i + 1$。如果 $i > |A|$，则跳到第8步。 4. 如果可以从 $s_i = \max(ans + 1, l_i)$ 开始执行任务 $i$，则执行此任务：$s_i = \max(ans + 1, l_i)$，$ans = s_i + t_i - 1$。然后继续处理下一个任务（第3步）。 5. 否则，寻找一个任务 $b_k$ 满足以下条件：首先，任务 $a_i$ 可以从 $s_i = \max(ans + 1, l_i)$ 开始执行；其次，值 $b_k$ 的结束时间减去当前时间为正且尽可能大，如果有多个任务符合条件，则选择编号最大的作为 $b_k$。 6. 如果能够选择到适合的任务 $b_k$，则用 $a_i$ 替换 $b_k$，并继续处理下一个任务（第3步）。 7. 如果找不到合适的任务 $b_k$，则跳过任务 $i$，继续（第3步）。 8. 返回 $ans$ 作为 $f(A)$ 的结果。 Polycarpus 对这些公式和定义感到困惑，所以他请求你模拟函数 $f$ 的执行，计算 $f(A)$ 的结果。

输入的第一行为整数 $n$，表示任务集合 $A$ 中的任务数量（$1 \le n \le 10^5$）。 接下来的 $n$ 行中，每行包含三个整数 $l_i$、$r_i$ 和 $t_i$（$1 \le l_i \le r_i \le 10^9$ 且 $1 \le t_i \le r_i - l_i + 1$），表示第 $i$ 个任务的描述。 保证对于任意任务 $j$ 和 $k$，如果 $j < k$，则 $l_j < l_k$ 且 $r_j < r_k$。

针对每个任务 $i$，输出一个整数，表示在函数 $f(A)$ 的第 $i$ 次循环中，任务 $i$ 的处理结果。在第 $i$ 行输出： - `0`：如果任务 $i$ 在第4步被成功添加。 - `-1`：如果任务 $i$ 无法被添加或替换（第7步）。 - $res_i$（$1 \le res_i \le n$）：如果在第6步通过替换成功处理任务，其中 $res_i$ 是集合 $A$ 中被选择做替换的 $b_k$ 的任务编号。 **本翻译由 AI 自动生成**