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

My code's logic and editorial's logic is the same, then too time limit exceeded!
Автор VandanRogheliya, история, 5 лет назад, По-английски

Sorry for this noob question, I am new to competitive coding. I want to know what in my code is causing "time limit exceeded". Link to my code

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

»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

Let me say, you are asking OS for two arrays of length $$$2000001$$$ in each test case, and you set the arrays' elements equal to 0, which is $$$O(n)$$$, in other words you are doing $$$2000001$$$ iterations for each test case, its just too much. You dont have to clear all the array, you just need to clear first $$$n+1$$$ elements.

Iv'e cleared that and submitted your solution, it works very fast.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I think his code got TLE due to his typo. I mean he intended to declare temp1 and temp2 with size 200001, but somehow he typed 2000001 accidentally and got TLE. I edited his solution 80785027

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      See the time, the solution runs in about 900ms(it luckily passes), but mine works in about 80ms, indeed you are right but the main problem that caused TLE was that he was doing $$$O(MaxN)$$$ iterations for each test case.

      → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      No, it was not a typo. I wanted that big array XD. Thank you for looking into my code!

      → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh, I got it! That is why most of the answers declare arrays globally of that size. Thanks for the fast response!

    → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

The constraint in the statement is 2e5, yours is 2e6! Edit temp1 and temp2 size to 2e5 then your problem could be solved!

→ Ответить