← 返回题目列表

Codeforces · 164/E

E. Polycarpus 和任务

中文机器翻译题面 查看原题

Polycarpus 有很多任务。每个任务由三个整数 li、ri 和 ti 来表征。三个整数 (li, ri, ti) 表示要执行任务 i,需要选择一个整数 si (li ≤ si; si + ti - 1 ≤ ri),则该任务将连续执行 ti 个时间单位,从时间 si 开始,直到时间 si + ti - 1(含)。换句话说,任务执行持续 ti 的连续时间段,应该不早于 li 开始,并且不晚于 ri 完成。

Polycarpus 的任务有一个令人惊讶的特性:对于任何任务 j、k(其中 j < k)lj < lk 且 rj < rk。

假设有一组有序的任务 A,包含 |A|任务。我们假设 aj = (lj, rj, tj) (1 ≤ j ≤ |A|)。另外,我们假设任务是通过随着数量的增加而增加 lj 来排序的。

让我们考虑以下递归函数 f,其参数是任务 A 的有序集,结果是整数。函数f(A)由贪心算法定义,下面以伪编程语言描述该算法。

- 第 1 步。$$\beta=\infty$$,ans = 0。
- 第 2 步。我们按照集合 A 中数量递增的顺序考虑所有任务。让我们定义当前任务计数器 i = 0。
- 步骤 3. 考虑下一个任务: i = i + 1。如果 i > |A|完成后,进入第8步。
- 步骤 4. 如果您可以从时间 si = max(ans + 1, li) 开始完成任务,则执行任务 i:si = max(ans + 1, li), ans = si + ti - 1, $$B = B U a _ { i }$$。转到下一个任务(步骤 3)。
- 步骤 5. 否则,找到这样的任务 $$b_{k} \in B$$,首先,任务 ai 可以在时间 si = max$$( f ( B \setminus b _ { k } ) + 1, l _ { i } )$$ 完成,其次,$$ans - f((B \cup a_i) \setminus b_k)$$ 的值为正数,取满足第一个条件的所有bk中的最大值。如果可以选择多个任务作为 bk,请选择 A 组中数量最多的任务。
- 第 6 步。如果您成功选择任务 bk,则 $$ans = f((B \cup a_i) \setminus b_k)$$, $$B = ( B \cup a_{i} ) \setminus b_{k}$$。转到下一个任务(步骤 3)。
- 步骤 7. 如果您没有成功选择任务 bk,则跳过任务 i。转到下一个任务(步骤 3)。
- 步骤 8. 返回 ans 作为执行 f(A) 的结果。

Polycarpus 被这些公式和定义所困扰,所以他要求你模拟函数 f 的执行,计算 f(A) 的值。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 105) — 集合 A 中的任务数量。

然后 n 行描述任务。第 i 行包含三个空格分隔的整数 li、ri、ti (1 ≤ li ≤ ri ≤ 109, 1 ≤ ti ≤ ri - li + 1) — 第 i 个任务的描述。

保证对于任何任务 j、k(考虑 j < k),以下条件成立:lj < lk 且 rj < rk。

输出

对于每个任务 i 打印一个整数——函数 f(A) 中循环第 i 次迭代(步骤 3)处理任务 i 的结果。在第i行打印:

- 0 — 如果您成功在步骤 4 中添加了任务 i。
- -1 — 如果您未能添加或替换任务 i(步骤 7)。
- resi (1 ≤ resi ≤ n) — 如果你设法替换任务(步骤 6):resi 等于任务编号(在集合 A 中),应选择 bk 并替换为任务 ai。

示例

输入 #1

5
1 8 5
2 9 3
3 10 3
8 11 4
11 12 2

输出 #1

0 0 1 0 -1

输入 #2

13
1 8 5
2 9 4
3 10 1
4 11 3
8 12 5
9 13 5
10 14 5
11 15 1
12 16 1
13 17 1
14 18 3
15 19 3
16 20 2

输出 #2

0 0 0 2 -1 -1 0 0 0 0 7 0 12