Getting TLE using MO's.Any chance of improvement? — HackerRank problem

Revision en2, by GLAYS, 2018-08-11 02:38:05

Here is the problem.

So basically you have an array of integers a[] of size n.

n <  = 1e5 and a[i] <  = 215 ( = 3, 2 * 104).

And you're given q <  = 5e4 queries of the form (x, l, r) for which the answer is the maximum value of x xor a[i] for l <  = i <  = r.

The editorial's solution is about persistent segment trees which I know nothing about.Before reading that I was trying to solve it using MO's algorithm + trie which has a complexity of O((n + q) * sqrt(n)) without counting the time to answer a query using the trie.Now q * sqrt(n) is fine but n * sqrt(n) is too much.Because n * sqrt(n) is caused by the movement of r to the right(which can reach n) I thought, is it possible to use the fact that all the numbers are <= 215 to improve the complexity?

If r moves to the right more than 215 times then at least one element is repeated right?

Is it possible to use this(or any other optimization) to get MO's algorithm to pass?

Here is my code.It passes 11 test cases out of 14 and the rest are getting TLE(actually it says segmentation fault but I think it's TLE).

Any other solution is welcome.

Thanks !

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English GLAYS 2018-08-11 02:38:05 17 Tiny change: ' value of xxora[i]xxora[i]x xor a[i] for $l<=' -> ' value of `x xor a[i]` for $l<='
en1 English GLAYS 2018-08-11 02:03:41 1292 Initial revision (published)