Correct and Query Timestamped Prices

### Problem Implement a `StockPrice` object that records a stock price for each timestamp. `update(timestamp, price)` adds a record or corrects the price already recorded at that timestamp. Updates can arrive out of timestamp order. `current()` returns the price at the greatest recorded timestamp, while `maximum()` and `minimum()` return the largest and smallest prices among the current records. Each query is called only after at least one update. ```cpp class StockPrice { public: StockPrice(); void update(int timestamp, int price); int current(); int maximum(); int minimum(); }; ``` ### Examples **Example 1:** ```text Calls: update(4,8), update(2,12), current(), maximum(), update(2,5), maximum() Results: void, void, 8, 12, void, 8 Explanation: Correcting the older record removes its obsolete high price. ``` **Example 2:** ```text Calls on a fresh object: update(7,9), update(7,3), current(), minimum() Results: void, void, 3, 3 Explanation: One timestamp retains only its newest correction. ``` ### Constraints - `1 <= timestamp,price <= 10^9`. - At most `10^5` total method calls. - Every query follows at least one update. ### Clarifying Questions Latest means greatest timestamp, not most recently received update. Identical prices at different timestamps remain separate records. ```hint Inspect the structure Which structure can remove exactly one old price when a timestamp is corrected? ``` ### Reasoning checkpoints - Distinguish the most recent timestamp from the most recently received update. - Make corrections affect every later query, including extrema shared by several timestamps. - Preserve the constructor and all four operations across an interleaved sequence of calls. ### Optional extensions What must an alternative implementation do to keep obsolete records from affecting later extrema queries?