AT_nikkei2019_final_h Homework Scheduling

从今天开始，第 $i$ 天称为 Day $i$。例如，今天是 Day $1$，明天是 Day $2$。 马子有 $N$ 个编号为 $1$ 到 $N$ 的作业。她从 Day $1$ 开始，每天选择并完成 $1$ 个作业。若在 Day $A_i$ 或更早完成第 $i$ 个作业，她可以获得 $X_i$ 分；若在 Day $A_i+1$ 或更晚完成，则只能获得 $Y_i$ 分。这里 $X_i > Y_i$。 马子想知道，对于每个 $k$（$1 \leq k \leq N$），在 Day $k$ 之前最多能获得多少分。请帮她计算。

输入通过标准输入给出，格式如下： > $N$ $A_1$ $X_1$ $Y_1$ $A_2$ $X_2$ $Y_2$ $\cdots$ $A_N$ $X_N$ $Y_N$

输出 $N$ 行。第 $k$ 行输出 Day $k$ 之前最多能获得的分数。

## 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq A_i \leq N$ - $1 \leq Y_i < X_i \leq 10^9$ - 输入的所有值均为整数。 ## 样例说明 1 对于每个 $k$，最优的作业完成顺序如下： - $k=1$ 时，在 Day $1$ 完成作业 $1$，可得 $10$ 分。 - $k=2$ 时，Day $1$ 完成作业 $2$，Day $2$ 完成作业 $1$，可得 $7+9=16$ 分。 - $k=3$ 时，Day $1$ 完成作业 $2$，Day $2$ 完成作业 $3$，Day $3$ 完成作业 $1$，可得 $7+3+9=19$ 分。 由 ChatGPT 4.1 翻译