The Street - March 14

I had a few issues with this question. First of all, if a shop is empty initially and a conservation fee is applied on it. Later on some items are added to this shop. Will this old conservation fee affect the prices of these new items ? I assumed it should but I was not sure.

My approach to the question was to have a hashmap of shop ids with shop object. Each shop object would contain the price of the costliest item along with the total conservation fees levied on that shop and a boolean variable to indicate if the item is available or not. I used this because there might be cases where the fees is levied first and no item has been added to the shop yet and in such cases I am storing the price as 0 by default but I keep available as false.
I saw a few solutions and everybody seems to have used segment trees. Can’t it be done the way I approached the problem ? I was getting a WA somehow.

Link to my solution : http://www.codechef.com/viewsolution/3617772

Either I missed a corner case or I probably did not understand the problem. Here’s hoping someone can explain it to me in case my interpretation was incorrect.

Maybe you’ve missed something, but anyway your solution will get TLE. You may have m / 2 shops and m / 2 updates which hit all shopps, so the complexity will be O(m^2). To make efficient updates on segment you should use treaps/segment trees.

//