Why getting TLE on O(n*log2(n)) solution?

general
1

I recently solved a problem in the coder’s legacy contest. I solved the problem
C( CodeChef: Practical coding for everyone ) in O(q*log2(n)) and getting TLE. Please tell me why??
Q–> queries, n = length of string(|S|)
This is my solution: CodeChef: Practical coding for everyone
Thanks in ADVANCE!!

2

same problem

3

Copied my comment from another post.
Complexity of both of my last 2 submissions of third problem (CLBRKT) were O(qlog(|s|)). The only difference between two submissions was a cin and scanf only for the input of number of test cases T.

The one with cin got TLE Submission
Other one with scanf got AC Submission

I am not sure why this happened and it costed me 1 hour of penalty time.

4

I did in O(n) and answered each query in O(1) and TC was 2.34 seconds (out of 3 seconds provided) in Java.

5

The problem statement clearly states that the input and output is large and hence the user must use fast input, output methods. scanf() is faster than cin.
Alternatively, you can use:
ios_base::sync_with_stdio(false);
cin.tie(NULL)
cout.tie(NULL)
Your TLE submission gets AC if we add these lines.
https://www.codechef.com/viewsolution/35690996

7

Using maps takes a lot of time. I was answering each query in O(1) by maintaining a map and yet I was getting TLE. I just used a vector instead of the map and got AC.
Here is link to my submission:
https://www.codechef.com/viewsolution/35686254

8

Can you please see my TLE solution?
I used scanf and printf for all inputs and outputs excepts for the number of test cases, did that anyhow cause me TLE? In my sense it shouldn’t.

9

That happened probably because of the strict time limit for this question.
Because even in my sense, it should not happen.

1 Like
10

The same happened with me, so finally to find the error i had just taken input and printed -1 for every query value.But still i got TLE,and i had used the fast input output codes.
Here’s a link to my submission.
https://www.codechef.com/viewsolution/35689520
What’s the problem can anyone tell

12

scanf("%s", s); <-- after adding this statement i was getting runtime error that is why i used cin for input of string.

13

Try using character array and not using unordered map.