Lately I have been solving this problem, lucky array. I implmented a O(m log n + 30 * n log n) where n, m <= 1e5(my submission). My solution got tle in some test cases. And I have found that the solution in the editorial is the same as mine. Then I tried using bottom-up segment tree instead of top-down but it didn't aid the issue.
I think the main reason that causes the tle is because the execution time is multiplied by 2. And that is too much. I had once encounter the same issue but with different tasks, I managed to optimized well and passed. But I couldn't this time. I think that maybe the time limit should be increased if the execution time have to be multiplied by 2 ? Or it would become a constant optimizing problem.
The reason for multiplied execution time is new testing servers, more powerful and fast
Have you tried to copy/paste a solution from other contestant?, I mean, you don't have to see the solution just copy-paste and submit, if that solution get accepted, then there is a solution fo the problem, could be with some constant optimizations, or maybe just another algorithm.
Of course I know there is a way to solve the problem. The main point is that the execution time calculated for old problems is not very fair. E.g. I just copied Arios's solution which pass in 3380 ms. Then I submit it again and it receive tle.
I tried to submit the same code with GNU C++14, in the hope, that the more advanced compiler will do some magic, but that also TLE'd...