予選 A-B 「step モード」

問題文はこちら。

まず、開始時刻 S_i、終了時刻 E_i として全てのスクリプトが S_i < E_i である場合、いつ巻き戻りが起きたのかそもそも 21:00:00.000 から 22:59:59.999 の間に起きたのか特定できないため全てのスクリプトについて出力は -1 となります。

次に巻き戻りが起きた可能性のある区間を算出します。E_i \leq S_i を満たす S_i のうち最も未来のものを S_r とし、同じく E_i \leq S_i を満たす E_i のうち最も過去のものを E_r とすると、巻き戻りが起きた可能性のある区間は (S_r,\ E_r) となります。

この区間にある開始時刻もしくは終了時刻は巻き戻り時刻よりも過去なのか未来なのかが判断できなくなります。

開始時刻もしくは終了時刻がどちらの時間軸か判断できない区間はもう 1 種類あります。下記の図は 21:10:13.300 ごろに巻き戻りが発生した場合の例ですが、赤く示された区間で開始時刻もしくは終了時刻がどちらの時間軸のものなのか判断できません。この区間は巻き戻りの発生から未来に 1 秒と過去に 1 秒の区間となります。ただし、巻き戻りの発生時刻が区間でしか分かっていないため、この判断のできない区間はそれぞれ (S_r - 1,\ S_r], [E_r,\ E_r + 1) となります。

よって、判断のできない区間の和は (S_r - 1,\ E_r + 1) となります。よって、S_i < E_i であるスクリプトのうち、この区間に開始時刻もしくは終了時刻を持つものについての出力は -1 となります。

それ以外の実行時間は、E_i \leq S_i を満たすものは E_i - S_i + 1、S_i \leq S_r かつ E_r \leq E_i を満たすものも E_i - S_i + 1、それ以外では E_i - S_i となります。