The inquiring manager challenge

You are responsible for auditing all customer orders. Each order has a price, P_i, and a timestamp, T_i, denoting the minute when it was received.

At any given time, your manager can ask you for the maximum price of any order placed within the last 60 minutes. For example, if your manager stops in at minute 83, you must know the maximum price of any order received between minutes 24 and 83. Observe that you must also account for orders received in the same minute as your manager arrived.

You are given a list of N events, where each event represents either a received order or an inquiry. For each inquiry from your manager, print the maximum price for any order placed within the last 60 minutes on a new line.

Input Format
The first line contains a single integer, N, denoting the number of events. Each of the N subsequent lines describes either of the following types of events:
1 P T – An order with price P was placed at time T.
2 T – Your manager stopped in at time T to inquire about the maximum order price for the last 60 minutes.
All the events are given in non-decreasing order with respect to T, so for i \textless j, we have T_i \le T_j.

If there are multiple events of different types occurring at the same time, the received orders will be listed before manager inquiries.

Constraints
1 \le N \le 10^6
0 \le P_i,T_i \le 10^{18}

Output Format
For each event of type 2, print a number denoting the maximum price for any order placed within the previous 60 minutes on a new line. If no orders were placed during that interval, print -1.

Assume there will be at least one event of type 2.

Sample Input

Sample Output

Explanation
The largest order price in time range \left[0,40\right] is 150.
The largest order price in time range \left[0,59\right] is still 150.
The largest order price in time range \left[1,60\right] is 143.
The largest order price in time range \left[2,61\right] is 159.
The largest order price in time range \left[61,120\right] is still 159.
There were no orders placed in time range \left[62,121\right], so we print -1 for this inquiry.

Solution
We will solve this using a Map time2price, with time2price[t] holding the maximum price at exactly time t. While we read our input we check if it is an order or inquiry. If we have an order we check if we already have a price for the current time t (as multiple orders can be made at the same time). If we already have a price we choose the maximum between the existing and the new price. If we do not have a price for t, we insert it into our map.

Since we don’t want our map to grow unnecessarily, we remove entries that we don’t consider relevant anymore every time we read a new price. Those entries are prices with a timestamp \textless t - 60. That way our map will hold a maximum of 60 entries at any given time.

Now, if we get an inquiry, we just need to search our map for the maximum price and print it.

Full code

 

lucas