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.