Train Reservation Reroute Auditor

Problem Statement

A national rail operator runs a single high-speed line with M consecutive segments numbered 1..M . Every segment starts the day with a cumulative cost of 0 . Throughout the day, N reservation events arrive in chronological order. There are two kinds of events: BOOK l r p — a passenger has booked a journey across segments [l, r] with a per-segment cost contribution of p . After this event, every segment in [l, r] increases its cumulative cost by p . QUERY l r — ask for the minimum cumulative cost among the segments in [l, r] as of right now, that is, reflecting all preceding BOOK events. The auditor wants to replay the day's log and emit one answer for every QUERY . It must also produce one final value, the threshold-event index t* : the earliest event index t such that, after the first t events have been applied, some segment's cumulative cost has reached or exceeded the threshold T (that is, is >= T ). If no segment ever reaches T , this value is -1 . The value is alway