### Namritaansh02's blog

By Namritaansh02, history, 2 months ago,

This is the problem. I am using sparse table and implementing it exactly as given in the editorial but I am getting, TLE on test 3. I have been stuck for 2 days now on this:-(

Can anyone point out the mistake? Thanks.

This is my submission : 124743771

• +5

 » 2 months ago, # |   +27 Let's look at the last for cycle in your solution. For every i your solution bruteforces all possible values of j (in increasing order). If array is something like this: $[2, 4, 6, 8, 10, ..., 2n]$ then for every i the correct j is n — i. In total, there would be $n + (n - 1) + ... + 1 = \frac{n(n - 1)}{2} = O(n^2)$ checks, it is too slow.Instead of this, you should binary search on j. Then you wouldn't check more than $O(n\log{n})$ indices, that is much better.NOTE: You might want to optimize your power function. It works in $O(\log{x})$, so if you will write binary search, the total complexity will be $O(n\log^2{n})$. It could also TLE. You can precompute all the logarithms in some array, thus deleting extra log factor.
•  » » 2 months ago, # ^ |   0 The power function could also be written like:return 31-__builtin_clz(x); to get rid of a factor of log(n)
•  » » 2 months ago, # ^ |   +8 Thanks a lot. Really understood well where I was going wrong.
 » 2 months ago, # |   0 I am also facing a similar difficulty. I've used a segment tree for this problem and I am getting TLE in test 5.My Submission. Any help would be appreciated!