The double action system operates as follows. When a new buy order of $x arrives it is simply stored for future use if none of the stored sell orders has an asking price lower than or equal to $x. Otherwise, the new buying bid is matched with the sell order with lowest asking price (earliest such order if there are ties). The two matched orders are removed from the system, and the buyer receives the item in exchange for paying a clearing price equal to the matched sell order asking price, i.e., the lowest asking price available at the time the new buy order was received.
Processing of a new sell order with an asking price of $y is done in a similar way. If all stored buying orders have a bid price strictly lower than $y, then no matches can be made and the new order is simply stored for possible future matching. Otherwise, the new sell order is matched with the stored buy order with highest bid price, handling ties as above. The two matched orders are again removed from the system, and the clearing price paid in this case is the bid price of the matched buy order, i.e., the highest bid price available at the time the new sell order was received. your program should require O(logn) time per order when processing a list of n orders.
Sample Input 1
order 1 sell at 30
order 2 buy at 20
Output for Sample Input 1
units exchanged 0 total clearing price 0
Sample Input 2
order 1 sell at 30
order 2 buy at 20
order 3 buy at 40
order 4 buy at 30
order 5 sell at 10
Output for Sample Input 2
units exchanged 2 total clearing price 60