TLE in DCGAME.Help Please...

I am getting TLE in DCGAME…
My code is here CodeChef: Practical coding for everyone
please help.Thnx in advance :slight_smile:

Kindly work on set,while you inserting.

set doesn’t work in linear way.

1 Like

can u please detaily tell me? it will be a greate help :slight_smile:

I think there is no use of set in this question. Also, sorting function should be avoided as the constant factor for it is large. As per the question your complexity may be O(nlogn) but since the time limit is strict, the constant factor should also be less. You can have a look at my solution. CodeChef: Practical coding for everyone

There is just one difference. Instead on using stack, I have used my own method of calculating the frequencies, using combinations formula. The cummulative frequency has been calculated and stored in array solve. Since map already stores the elements in sorted order, there was no need of sorting function in my solution. Also, map queries are O(logn) to avoid TLE is task 2 of subtask 3, as it is happening in your case (which also happened with me earlier), avoid using maps inside the query. Just binary search and answer the query in O(1). Also since (n*(n+1)/2) was needed many a times in the solution, especially for “>K” queries, I stored it’s value in total variable to avoid unnecessary calculation overhead. Hope it helps.