svg_af's blog

Help with TL on sum of distinct digits in range
By svg_af, history, 9 years ago, In English

Hello there

I'm trying to solve this problem with this code

Now what I'm doing is building a segment tree with a treap in each node that keeps the position of the next equal number in the array for every number in range

after numerous WAs i got TL and while testing my code on extreme cases i found out it really does take a very long time to execute for 50000 ... the extreme case

My code's complexity is supposedly N*log^2(N) which should be fast for this size of input

what am i doing that's so slow ??

please help :/

UPDATE ::

I used a different approach for insertion and deletion on treaps where if a node already exists i only increase its value instead of inserting a another node

that got the runtime to around 14 seconds on the extreme testcase that never ended with my previous code

but it's still too much for O(nlog^2n) complexity ...

what am i doing wrong and if that's not the way what is ???

here's my current code

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

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I should mention that i tried coding AVL trees instead of treaps and it's as slow ... and i noticed while debugging that what takes time is the inserting operations

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

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

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

seriously any help would be appreciated ... is Nlog^2n too much for input of size 50000 and 100000 queries ??

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

I tried it too with segment tree and an AVL in each node, but got TLE too .
Any help about how to do this problem would be highly appreciated I spent too much time on it but never got AC .

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Edit: Ignore, did not see update queries :O

Try Mo's algorithm + coordinate compression

→ Reply