← 返回题目列表

AtCoder · abc217_h

H. 潜龙漫画

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

分数: 600 点

问题陈述

在 AtCoder, Inc. 开发的一款名为 Snuketoon 的游戏中,玩家扮演 Snuke 来躲避水枪的水。

平台由无限数线组成,Snuke 位于该点 0 在游戏开始时。
从游戏一开始,Snuke每秒可以做出三个动作之一:移动 1 向负方向移动 1 朝正方向,或保持静止。更正式地说,如果 Snuke 的位置是 p at t 秒 (t \geq 0, t 是一个整数)从游戏开始,他的位置为 t+1 秒即可 p-1, p,或 p+1.

Snuke 因被水枪浸湿而受到伤害。水枪射击 N 次,并且 i第一个镜头表示为 T_i, D_i,和 X_i 如下。

  • At T_i 比赛开始后几秒,水从左边或右边射出。让 p 是Snuke当时的位置。如果他处于以下范围内,他会受到以下伤害。
    • 当 D_i = 0,他采取 X_i - p 点伤害(如果他在范围内) p \lt X_i.
    • 当 D_i = 1,他采取 p - X_i 点伤害(如果他在范围内) X_i \lt p.

高桥是一名职业玩家,他希望在比赛结束后将 Snuke 受到的总伤害降到最低 N第一个镜头,发布关于此游戏的推文。求游戏进行时 Snuke 受到的总伤害,以将其最小化。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T_1 \lt T_2 \lt \dots \lt T_N \leq 10^9
  • D_i (1 \leq i \leq N) is 0 or 1.
  • -10^9 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
T_1 D_1 X_1
T_2 D_2 X_2
\vdots
T_N D_N X_N

输出

打印玩游戏时 Snuke 受到的伤害点数,以将其最小化。


示例输入 1

3
1 0 3
3 1 0
4 0 6

示例输出 1

7

为了方便起见,让 t 表示从游戏开始起经过的秒数。在完成所有射击之前,Snuke 的最佳移动路线如下。

  • 当 t = 0,Snuke 就在这个点上 0。他动了 1 正方向。
  • 当 t = 1,Snuke 就在这个点上 1 并采取 2 第一次射击造成的伤害。他动了 1 负方向。
  • 当 t = 2,Snuke 就在这个点上 0。他仍然一动不动。
  • 当 t = 3,Snuke 就在这个点上 0 并且第二次射击不会造成任何伤害。他动了 1 正方向。
  • 当 t = 4,Snuke 就在这个点上 1 并采取 5 第三次射击造成的伤害。

在这里,Snuke 总共需要 7 点伤害,所以你应该打印 7.


示例输入 2

3
1 0 1
6 1 1
8 0 -1

示例输出 2

0

示例输入 3

5
1 0 1000000000
2 1 -1000000000
3 0 1000000000
4 1 -1000000000
5 0 1000000000

示例输出 3

4999999997