RajiunNabi's blog

By RajiunNabi, history, 12 days ago, In English

so the problem is from cses problem set. Link is https://cses.fi/problemset/task/2134/ Don't know why it is giving Tle. the time complexity of this heavy light decompostion is log2^2(n)*n.Help me guys. And here is my code for this problem https://ideone.com/6Gky4v

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RajiunNabi (previous revision, new revision, compare).

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It depends on the judge's speed and your constant factor. E.g. an optimized $$$O(nlogn)$$$ will pass but a multiset solution (with $$$O(nlogn)$$$ complexity) won't pass 1926D - Vlad and Division. Edit: CSES's judge is slower than CodeForces. Also the multiset TLE isn't about the constant factor, I just checked for existence using count, which is extremely inefficient.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dude what are you saying. I don't even use an multiset

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used segment tree and heavy light trick which will get a log(n)^2 * n complexity