jlcastrillon's blog

Data Structure Problem
By jlcastrillon, 11 years ago, In English

Hi I have been trying to solve this problem http://www.spoj.com/problems/KL11B/ The solution I have found so far uses BIT + Treap(Balanced Tree) and worst case complexity is log^2(n) for each query. Some users have accepted the problem using a lot less time and memory than other users that I know they used this solution. Is there a faster solution to this problem or it was just constant optimization?, would there be a faster to code solution to this problem having at most log^2(n) complexity for each query.

  • 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

oops. It was wrong soory, I didn't get statement clearly.

ADD: Using BIT + Treap got AC code

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

Really nice implementation, but your time is three times greater than best solution. I wonder what they implemented to get that time..

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

    My best was 15.2 secs, you can implement treap non-recursively, it should be much more faster.

    → Reply