H - Snuketoon Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

AtCoder 社が開発したゲーム『スヌケトゥーン』は、プレイヤーがすぬけ君を操作して水鉄砲から飛んでくる水を回避するゲームです。

ゲームのステージは無限に続く数直線からなり、ゲーム開始時点ですぬけ君は地点 0 にいます。
ゲーム開始直後から、すぬけ君は 1 秒ごとに「 1 小さい地点に移動」「 1 大きい地点に移動」「動かない」の 3 択から行動を選べます。より厳密には、すぬけ君がゲーム開始後 t 秒 (t \geq 0, t は整数) の時点で地点 p にいるとき、 t+1 秒の時点では地点 p-1 ・地点 p ・地点 p+1 の 3 ヵ所のいずれかに行くことができます。

すぬけ君は水鉄砲から発射された水を浴びるとダメージを受けてしまいます。水鉄砲は N 回発射されて、 i 回目の発射は T_i, D_i, X_i を用いて次のように表されます。

  • ゲーム開始から T_i 秒後に左右いずれかから水が発射されます。すぬけ君が T_i 秒の時点でいる地点を p としたとき、ダメージを受ける範囲および値は次の通りです。
    • D_i = 0 のとき、p \lt X_i の範囲にいると X_i - p のダメージを受ける。
    • D_i = 1 のとき、X_i \lt p の範囲にいると p - X_i のダメージを受ける。

プロゲーマーの高橋君は、攻略情報をツイートするために N 回目の水鉄砲の発射が終わった後のすぬけ君の合計ダメージを最小化することにしました。高橋君が合計ダメージを最小化するようにすぬけ君を操作したときの合計ダメージを求めてください。

制約

  • 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

出力

高橋君が合計ダメージを最小化するようにすぬけ君を操作したときの合計ダメージを出力せよ。

入力例 1

3
1 0 3
3 1 0
4 0 6

出力例 1

7

便宜上 t をゲーム開始から経過した秒数を表す変数とします。全ての水鉄砲の発射が終了するまでのすぬけ君の最適な動きは以下の通りです。

  • t = 0 のときすぬけ君は地点 0 にいます。すぬけ君は 1 大きい地点に移動します。
  • t = 1 のときすぬけ君は地点 1 にいて、 1 回目の水鉄砲の発射により 2 のダメージを受けます。すぬけ君は 1 小さい地点に移動します。
  • t = 2 のときすぬけ君は地点 0 にいます。すぬけ君は移動しません。
  • t = 3 のときすぬけ君は地点 0 にいて、 2 回目の水鉄砲の発射によるダメージを受けません。すぬけ君は 1 大きい地点に移動します。
  • t = 4 のときすぬけ君は地点 1 にいて、 3 回目の水鉄砲の発射により 5 のダメージを受けます。

このときすぬけ君は合計で 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

Score : 600 points

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