H - Snuketoon

分数：600分

问题描述

在由 AtCoder 公司开发的一款名为 Snuketoon 的游戏中，玩家扮演 Snuke 在躲避水枪的水攻击。

游戏平台由一个无限数量的数轴组成，开始时 Snuke 位于点0。
从游戏一开始，Snuke 每秒可以进行以下三种移动之一：向负方向移动1个单位，向正方向移动1个单位，或保持不动。具体来说，如果在游戏开始的时间 $t$ 秒（$t \geq 0$，$t$ 是整数）Snuke 的位置是 $p$，那么在 $t+1$ 秒的位置可以是 $p-1$，$p$ 或 $p+1$。

Snuke 会从被水枪浇湿而受伤。水枪总共射击 $N$ 次，第 $i$ 次射击由 $T_i$，$D_i$ 和 $X_i$ 表示，如下所示。

• 从游戏开始的 $T_i$ 秒，水枪会从左边或右边射击。令 $p$ 为 Snuke 的此时位置。如果他在以下范围内，他会受到以下伤害：
  • 当 $D_i = 0$ 时，如果他在范围 $p \lt X_i$ 内，他会受到 $X_i - p$ 的伤害。
  • 当 $D_i = 1$ 时，如果他在范围 $X_i \lt p$ 内，他会受到 $p - X_i$ 的伤害。

Takahashi 是一名职业玩家，他希望在第 $N$ 次射击结束后，Snuke 受到的总伤害最小，以便在游戏中发表一条推文。找到使得伤害最小的情况下 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)$ 是 $0$ 或 $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 在玩游戏以最小化伤害时受到的伤害点数。

3
1 0 3
3 1 0
4 0 6

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。

3
1 0 1
6 1 1
8 0 -1

0

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

4999999997