I don’t understand why segment tree implementation gives TLE for chef and strings(STRQ). Here is the link to my code. Please have a look. http://ideone.com/62RGET
Precomputation gets AC.
I don’t understand why segment tree implementation gives TLE for chef and strings(STRQ). Here is the link to my code. Please have a look. http://ideone.com/62RGET
Precomputation gets AC.
Segment tree in NlogN buiding time + logN query while pre computation takes linear building time and constant query time. So thats why!
Building time of segment tree is O(n) and n in this question is 10^6, so O(nlogn) should work fine in 1 sec
O(nlog(n)) works fine with 10^5, not 10^6.
Since the number of queries are 10^6, you need a constant time algo.
Thanks. Now I get it.