Hi,
I had made this problem( https://www.codechef.com/FTCF2020/problems/TRADE2 ) and the approach that I used to solve was make a segment tree over a multiset table of size 10^5. In that approach , table[i] would denote prices of phones with speed i. Segment tree would work on the .begin() values of the multiset tables.
I wanted to know if there's any alternate approach to this problem. Thanks in advance!
We can solve it offline by taking a list of all phones (even ones that are held by customers) and sorting it by speed. Additionally, each phone has an "active" boolean indicating whether it is currently able to be bought. Now, we need to perform queries of the following form:
We can do this with a segment tree, where each node stores the index corresponding to an active phone with minimum price on an interval. The details are not that difficult.
To process a customer, we use binary search to find the leftmost element in the array satisfying our speed conditions, and then query the segment tree to get the best phone on the corresponding suffix. Then toggle the activity of both the phone we came into the shop with, as well as the phone we just found.
Total running time is $$$O(n+q\log(n+q))$$$.
Thanks for sharing the approach.
Can you allow submissions for the problems?
I can't do it. Codechef will do it by tomorrow. I'll reply here once it becomes active.
You can submit now.
Got it thanks :)