## Problem A highway has checkpoints numbered `0` through `m - 1` in road order. `segmentFees[i]` is the toll for traveling between checkpoints `i` and `i + 1` in either direction. You receive one day's checkpoint records in chronological order. Each record is `[license, checkpoint]`. For every vehicle, charge the road distance between each pair of its consecutive records. A vehicle may reverse direction or report the same checkpoint repeatedly. Return the total toll across all vehicles for the day. ### Function Contract Implement `totalDailyToll(segmentFees, records)` and return one integer. ### Constraints & Assumptions - `1 <= m <= 200,000`; `len(segmentFees) == m - 1`. - `0 <= segmentFees[i] <= 10^9`. - `0 <= len(records) <= 200,000`. - Every checkpoint is in `[0, m - 1]` and each license is a nonempty ASCII string. - The answer may exceed signed 32-bit range. - The records are already in the exact time order to process. ### Clarifying Questions to Ask - Is travel direction relevant to price? No, segment fees are symmetric. - Does the first record for a vehicle incur a charge? No. - What does a repeated record at the same checkpoint cost? Zero. ```hint Precompute distances from checkpoint zero A prefix sum of segment fees makes the toll between checkpoints `a` and `b` equal to `abs(prefix[a] - prefix[b])`. ``` ```hint Remember only each vehicle's last checkpoint Process the global record stream once. Charge from the stored checkpoint, then replace it with the current one. ``` ### Example ```text segmentFees = [5, 7, 2] records = [ ["A",0], ["B",3], ["A",2], ["A",1], ["B",1], ["A",1] ] A pays 12 + 7 + 0; B pays 9; total = 28 ``` ### Evaluation Focus - Uses per-license chronological adjacency, not adjacency in the global log alone. - Handles forward, reverse, and zero-distance travel. - Uses prefix sums for constant-time pair cost. - Runs in `O(m + number of records)` expected time. ### Extensions to Discuss 1. How would you process records that arrive out of timestamp order? 2. How would daily caps or vehicle-specific rates change the state? 3. How could the calculation be partitioned across workers without splitting a vehicle's sequence incorrectly?