catlak_profesor_mfb's blog

Optimizing Treap Code
By catlak_profesor_mfb, 10 years ago, In English

I am trying to solve this treap problem. http://poj.org/problem?id=3580 But it is getting TLE, though I think my solution is O(nlogn). If the code is poorly written how can I optimize it? Thanks for your help. Here is my code: http://paste.ubuntu.com/8533067/ Update: I got accepted by using an overloaded new operator(allocated 40mb at first). Here is accepted code: http://paste.ubuntu.com/8539750/

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

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Maybe if node objects will be close in memory, it'll be faster. I would try to allocate treap nodes in one array.

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

    Well I just submitted my code with an overloaded new operator as you said. And got accepted. Thanks.

    → Reply