accepted solution solution with TLE
The two given solutions, don’t have much difference, yet one gives TLE while other gets accepted very easily. I wonder why so ?
Does multiset.end( ) have a non-constant time complexity ?
cin.tie(0);
cout.tie(0);
If you only include these lines in your TLE code, then your solution will get accepted.
No. end() does not have non-constant time complexity. It has constant time complexity.
Thanks for this, though I had never seen such a huge time difference by just adding cin.tie(0) and cout.tie(0) ! I wonder what data-structure should be used to make the solution accepted without these two . 
/
I think the data structure is efficient enough but the in the codechef, for many programs we have to use fast i/o. Happened to me in last long contest. In problem SJ1 I didn’t use fast I/O and hence TLE was coming. But when I used fast i/o only I got it accepted.
1 Like
as we know that the implementation of multiset is in the form of r-b tree,and since the values stored in a tree are not in continuous memory locations therefore it takes O(N) time
per operation to traverse in worst case from one value to another…therefore it gives TLE…
check if u have used such library functions which have O(log N) complexity,since they will work in O(N) on implementing on multiset instead of O(log N) hence it is givingh TLE:)