Let us first consider a naive DP (Dynamic Programming).

• \(dp_{i, x} :=\) minimum damage to reach \(x\) after \(T_i\) seconds

For convenience, let \(T_0 = 0\). Then we have the following transitions.

\[ dp_{i, x} = \begin{cases} 0 & i = 0 \wedge x = 0 \\ \infty & i = 0 \wedge x \neq 0 \\ \displaystyle \min_{ |y - x| \leq T_i - T_{i-1} } dp_{i-1,y} + \max(0, X_i - x)& i \gt 0 \wedge D_i = 0 \\ \displaystyle \min_{ |y - x| \leq T_i - T_{i-1} } dp_{i-1,y} + \max(0, x - X_i) & i \gt 0 \wedge D_i = 1 \end{cases} \]

If we naively compute this DP, we can find it in a total of \(\mathrm{O}(\max(T)^2)\) time, but of course it will lead to TLE.

Here, for some fixed index \(i\) of DP table, let us plot \((x, d_{i,x})\) on \(xy\)-plane for the range \(-T_i \leq x \leq T_i\) and connect them with segments. Then, the resulting shape is a convex function consisting of \(\mathrm{O}(i)\) straits lines. Indeed, defining a function

• \(f_i(x) :=\) a function satisfying \(f_i(x) = dp_{i,x}\) for all \(-T_i \leq x \leq T_i\),

we can replace the DP above using \(f(x)\) as follows, which recursively proves that \(f_i(x)\) is a convex function within the range \(-T_i \leq x \leq T_i\). (Here, \((X_i-x)_{+}\) denotes \(\max((X_i-x),0)\).)

\[ f_i(x) = \begin{cases} 0 & i = 0 \\ \displaystyle (X_i - x)_{+} + \min_{ |y - x| \leq T_i - T_{i-1} } f_{i-1}(y) & i \gt 0 \wedge D_i = 0 \\ \displaystyle (x - X_i)_{+} + \min_{ |y - x| \leq T_i - T_{i-1} } f_{i-1}(y) & i \gt 0 \wedge D_i = 0 \\ \end{cases} \]

Such DP can be computed by simulating the convex function with a technique called Slope Trick, in which the changing points are managed with two priority queues.

There is a good editorial of Slope Trick in Japanese written by maspy, which is really easy to understand, and also includes many past problems of AtCoder using this trick. For English speakers, refer to this Codeforces article.

As described above, there are already splendid materials about Slope Trick, so we do not explain it here. Therefore, the problem has been solved in a total of \(\mathrm{O}(N \log N)\) time.

A sample code in Python is shown below. (In order to get AC for the following submission, you have to choose PyPy3 runtime.)

import heapq
import sys

L, R, addL, addR, miny = list(), list(), 0, 0, 0

def push_left(x):
  heapq.heappush(L, -x + addL)

def push_right(x):
  heapq.heappush(R, x - addR)

def top_left():
  return -L[0] + addL

def top_right():
  return R[0] + addR

def pop_left():
  return -heapq.heappop(L) + addL

def pop_right():
  return heapq.heappop(R) + addR

def add_xma(a):
  global miny
  if len(L) != 0:
    miny += max(0, top_left() - a)
  push_left(a)
  push_right(pop_left())

def add_amx(a):
  global miny
  if len(R) != 0:
    miny += max(0, a - top_right())
  push_right(a)
  push_left(pop_right())


it = map(int, sys.stdin.buffer.read().split())
N = next(it)
L.extend([0] * (N + 10))
R.extend([0] * (N + 10))

t = 0
for T, D, X in zip(it, it, it):
  addL -= T - t
  addR += T - t
  if D == 0:
    add_amx(X)
  else:
    add_xma(X)
  t = T

print(miny)