Yesterday I was doing a question 86D - Powerful array.
I implemented Mo's algorithm and got TLE in java. Then after some modifications in got accepted in 4740 ms (27581138). I started seeing the solution of others users to find ways to optimize my code so that it gets accepted in less time. I came across this solution (14855687) which passed in 2306 ms (almost half). I tried my best to do exactly the same but still my code runs in almost the same time as earlier. This time it was around 4802 ms (27581630).
Can anybody tell me what exactly is the reason behind this and what should I do to pass my submission in less time?
Thanks in advance!
It's because you're doing two division in every compare (for sorting queries I guess), but that red guy doesn't!
I didn't understand that. I calculated the block number whenever the compare function is called whereas the red guy has precalculated it. All of this happens in O(1) how does it effect the performance of the compare function?
division is fast, but it's relatively slow compared to sum or compare. Let's say it's 4x slower than compare, hence in a compare you are 4x (division) + 4x (division) + 1x (compare) = 9x slower than simple compare which in total gives you 9*nlgn time for sorting the array. Why don't you test it?
I tested your code and found that functions "add" and "remove" are bottlenecks.
How about if you change arr,count's type from long[] to int[]?
This did help alot,the submission time now was 3710ms 27630406. but still its much more and can you also please explain how does converting an array from long to int decreases the time by 1 sec?
I don't know this is accurate explanation. The code calls "add" and "remove" about 90M times, then "count[]" is also accessed about 90M times. When the array is accessed, some contiguous units of array are loaded together. These work as a cache. Changing from long[] to int[] makes the array improving accessibility.