Блог пользователя Bedge

Автор Bedge, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The reason for multiplied execution time is new testing servers, more powerful and fast

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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...