Editorial for Car Selection

This problem can be solved using the Greedy approach.
We will maintain a multiset for storing the points of each car. When a car of point xx arrives, the price of the car can be calculated by finding the largest point x\leq x and the smallest point x\geq x in the multiset. These can be done by finding the upper bound and the element before the upper bound of xx in the multiset. After that, the point xx will be inserted into the multiset. We will also maintain two heaps (priority_queue) in our solution. One is for Alice and the other is for Bob. The two heaps can be maintained differently by using the custom comparator as per the choices of Alice and Bob [Note: In C++, taking priority queues of pairs is enough. Hint: If you push negative values in the priority queue, the top element will have the minimum absolute value.]. In the case of query types 2 & 3, cars can be selected from their respective heaps. When a car is selected and removed from the shop, its corresponding points will also be removed from the multiset.

Time complexity: O(T×Q× log(n))O (T \times Q \times \ log(n) )

[P.S: In C++, using set/multiset instead of the heap (priority queue) may lead to TLE due to its slow nature. In this problem, set/multiset takes almost 2x2x time compared to the time taken by the priority queue.]

Statistics


53% Solution Ratio

Farhan20Earliest, 2M ago

mahdi.hasnatFastest, 1.1s

TurinhstuLightest, 112 MB

zh_rifatShortest, 2312B

Toph uses cookies. By continuing you agree to our Cookie Policy.