Блог пользователя svg_af

Автор svg_af, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 .

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Edit: Ignore, did not see update queries :O

Try Mo's algorithm + coordinate compression