No.631

横軸を時刻, 縦軸を駅としたグラフを描いてみると, 下のようになる.

各駅の始発電車の時刻を横幅とした長方形を置くと, 青線のように移動してもいいが, 赤線のように移動しても駅 $N$ に着く時刻は変わらない.

すなわち, $T_i-3(i-1)$ の最大値の時間だけ駅1で待機すれば後はすべての駅で待機することなく駅 $N$ に着くことができるということになる.

あとは最大値を求める遅延伝播付きのセグメントツリーに $T_i-3(i-1)$ を入れておき, 電車遅延が発生するごとに全区間の最大値を求めていけばいい.