TLE in DEVU AND CHURU

My time complexity is O(nlogn) and I am getting TLE in the second case of the 3rd subtask,
How is it possible as my code is in within time constraints.

Refer to the comments given below.

The contest is in progress. Remove it

You are not supposed to post anything related to the contest. Please kindly do remove it.

Hi s24w,

if you have any query related to ongoing contest then do comment in contest comment box DO NOT POST ANYTHING ANYWHERE ON WEB.

but i wanna tell you that although your complexity is O(n(long(n))) but dont forget about constant factor of complexity that play role here. you are failing in special border cases.

i hope you got :slight_smile:

TLE might be cause of some other reasons… Check your code. Its acceptable on O(nlogn).
Cheers… :slight_smile:

Check if it is slowing due to slow input/output…my solution had similar problem…changed cin to scanf…got AC…

TLE was coming due to STL MAP. So I removed it and got AC.

1 Like

I don’t understand why does codechef make such test cases that we have to use fast i/o. STL map has to be replaced by binary search. The complexity remains the same. What is the use of forcing us to make such optimizations when the overall complexity of the solution remains the same.

if u were using map …it will cause tle…as map sorts the data…u should have used unordered_map…

You can still get AC using map by using fastest I/O.
Here is one solution that I found - CodeChef: Practical coding for everyone