### pritishn's blog

By pritishn, 6 weeks ago, ,

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!

• +13

 » 6 weeks ago, # |   +3 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: toggle a single element from active to inactive, or vice versa. ask for the minimum price on a suffix, only taking into consideration elements which are active. 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))$.
•  » » 6 weeks ago, # ^ |   0 Thanks for sharing the approach.
 » 6 weeks ago, # |   0 Can you allow submissions for the problems?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I can't do it. Codechef will do it by tomorrow. I'll reply here once it becomes active.
•  » » 6 weeks ago, # ^ |   0 You can submit now.
•  » » » 6 weeks ago, # ^ |   0 Got it thanks :)