102177: [AtCoder]ABC217 H - Snuketoon

Problem Statement

In a game called Snuketoon, developed by AtCoder, Inc., the player plays as Snuke to dodge water from water guns.

The platform consists of an infinite number line, and Snuke is at the point $0$ at the beginning of the game.
Starting from the beginning of the game, Snuke can make one of the three moves in each second: move $1$ in the negative direction, move $1$ in the positive direction, or remain still. More formally, if Snuke's position is $p$ at $t$ seconds ($t \geq 0$, $t$ is an integer) from the beginning of the game, his position at $t+1$ seconds can be $p-1$, $p$, or $p+1$.

Snuke takes damage from getting soaked by water guns. The water guns shoot $N$ times, and the $i$-th shot is represented by $T_i$, $D_i$, and $X_i$ as follows.

• At $T_i$ seconds from the beginning of the game, water is shot from the left or right. Let $p$ be Snuke's position at that time. He takes the following damage if he is in the following range.
  • When $D_i = 0$, he takes $X_i - p$ points of damage if he is in the range $p \lt X_i$.
  • When $D_i = 1$, he takes $p - X_i$ points of damage if he is in the range $X_i \lt p$.

Takahashi, a pro gamer, wants to minimize the total damage taken by Snuke after the end of the $N$-th shot, to post a tweet on this game. Find the total damage taken by Snuke when the game is played to minimize it.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of points of damage taken by Snuke when the game is played to minimize it.

Sample Input 1

3
1 0 3
3 1 0
4 0 6

Sample Output 1

7

For convenience, let $t$ denote the number of seconds elapsed from the beginning of the game. The optimal course of movements for Snuke until all the shots are done is as follows.

• When $t = 0$, Snuke is at the point $0$. He moves $1$ in the positive direction.
• When $t = 1$, Snuke is at the point $1$ and takes $2$ points of damage from the first shot. He moves $1$ in the negative direction.
• When $t = 2$, Snuke is at the point $0$. He remains still.
• When $t = 3$, Snuke is at the point $0$ and takes no damage from the second shot. He moves $1$ in the positive direction.
• When $t = 4$, Snuke is at the point $1$ and takes $5$ points of damage from the third shot.

Here, Snuke takes a total of $7$ points of damage, so you should print $7$.

Sample Input 2

3
1 0 1
6 1 1
8 0 -1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

4999999997

问题描述

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

游戏平台由一条无限数轴组成，游戏开始时Snuke在点0处。

从游戏开始起，Snuke可以在每秒做出以下三个动作之一：向负方向移动1，向正方向移动1，或原地不动。更正式地说，如果Snuke在游戏开始后的t秒（t≥0，t为整数）的位置为p，则他在t+1秒的位置可以为p-1，p或p+1。

Snuke在被水枪打湿时会受到伤害。水枪射击N次，第i次射击用T_i，D_i和X_i表示如下。

• 在游戏开始后的T_i秒，水从左或右射出。设Snuke在那时的位置为p。如果他处于以下范围，他会受到以下伤害：
  • 当D_i=0时，如果他在范围p<X_i内，他受到X_i-p点伤害。
  • 当D_i=1时，如果他在范围X_i<p内，他受到p-X_i点伤害。

职业游戏玩家Takahashi想在游戏结束时使Snuke受到的总伤害最小，以便发布一条关于这款游戏的推文。找到当游戏结束时，Snuke受到的最小总伤害。

约束

• 1≤N≤2×10^5
• 1≤T_1＜T_2＜⋯＜T_N≤10^9
• D_i(1≤i≤N)为0或1。
• -10^9≤X_i≤10^9(1≤i≤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