← 返回比赛

已结束 GESP挑战赛#20

← 上一题下一题 →

A5077 | $午枫的彩排$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小午和小枫参加了一场彩排，这次彩排共有 $n$ 个人，每个人有能力值 $w_i$ ，每个人的入场时间为 $s_i$ ，退场时间为 $t_i + 0.1$ 。根据每位演员的表现，最终都会获得一个评分 $val_i$ 。同一时刻最多只会入场一位演员，每位演员会在 $s_i$ 时刻准时入场，会在 $t_i+0.1$ 时刻退场。 当一位演员 $x$ 入场时，演员 $x$ 会帮助这一时刻还在场的其他演员，但每位演员的能力有限，演员 $x$ 只能帮助能力值不超过他的其他演员。记这一时刻被帮助的演员中最小能力值为 $minw$ ，那么演员 $x$ 的评分 $val_x$ 为 $w_x-minw$ ，若演员 $x$ 没有帮助其他演员，则 $val_x$ 为 $0$ 。 小午和小枫想知道所有演员都彩排完毕后，这 $n$ 位演员的评分是多少。

输入格式

第一行输入一个正整数 $n$ $(1\leq n\leq 10^6)$ ，表示彩排的人数。 接下来 $n$ 行，每行输入三个正整数 $w_i,s_i,t_i$ $(1\leq w_i\leq 10^5,1\leq s_i< t_i\leq 10^9)$ ，分别表示第 $i$ 个人的能力值、入场时间、退场时间，保证 $s_i$ 各不相同。

输出格式

输出一行 $n$ 个整数 $val_i$ ，表示第 $i$ 个人最终获得的评分。

输入输出样例

输入 #1

输出 #1

0 0 3 0 5

C++ 编辑器

输入

输出