SeyedParsa's blog

346C — Time Limit
By SeyedParsa, 11 years ago, In English

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!

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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!

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply