Score : $600$ points

问题描述

在由AtCoder, Inc.开发的一款名为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$秒时，水枪从左边或右边发射水柱。假设此时Snuke的位置为$p$，若他在以下范围内，则受到如下伤害：
  • 当$D_i = 0$时，若他在范围$p < X_i$内，则受到$X_i - p$点伤害。
  • 当$D_i = 1$时，若他在范围$X_i < p$内，则受到$p - X_i$点伤害。

职业游戏玩家高桥想要最小化在第$N$次射击结束后Snuke受到的总伤害，以便在游戏中发推文。请计算当游戏以最小化伤害的方式进行时，Snuke所受到的总伤害。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:38:10