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

Автор SeyedParsa, 10 лет назад, По-английски

Hi!
I wonder why this submission(5616462) gets TL for problem 346C - Number Transformation II.
Isn't it true that the order of this code is almost O ((a-b) log(a-b)) which is equal to O(10^6 * log(10^6))?

UPD. Found my answer in this comment, Thanks!

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

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

Hi !

STL vector is slow in push_back while it's size is small. ( I_love_natalia said it at This blog )

look at your code in this submission(5623952) ! you will got it ...

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thanks! ;)
    I hadn't seen that blog and I had exactly the same problem, but I still got TLE after reserving memory, so I changed my algorithm!

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

std::map<> is also slow (if the log factor depends on it, there'll be a large constant factor to the complexity of the code), and queue<> can have the same reallocation issues as vector<> (I failed 372C - Watching Fireworks is Fun on that).