Help with TL on sum of distinct digits in range

Правка en2, от svg_af, 2016-02-10 00:51:06

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

Теги segment tree, treap, tle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский svg_af 2016-02-10 00:51:06 461
en1 Английский svg_af 2016-02-09 17:02:28 659 Initial revision (published)