Блог пользователя M.A.H.M.O.O.D

Help in figuring out an unexpected run time error in 455D serega and fun
Автор M.A.H.M.O.O.D, история, 7 лет назад, По-английски

Hello everyone.

I've been trying to solve this problem 455D - Serega and Fun but I keep getting RE on test case #9.

I don't know what's wrong with my code could someone please help me in figuring out what's wrong or atleast give me a test case where my solution breaks ??

Here's my submission : 27468511

Thank you very much for reading.

:)

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

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

could you please explan you're approach i didnt understand it

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    My idea is to divide the array to sqrt(n) blocks then do the following:

    For the first type of queries traverse the sqrt(n) blocks and shuffle the numbers between them that would result in a total of O(sqrt(n) * sqrt(n) * log(sqrt(n)) = O(n * log(sqrt(n)) complexity the first sqrt(n) is because of traversing the sqrt(n) blocks, second is because we have to insert a new element in the beginning of each block and remove one at the end of it and the log factor comes from updating the occurrences map in each block.

    For the second type of queries I keep a map of occurrences in each block so I just have to traverse each block and see what is cnt[k] in each one which will result in O(sqrt(n) * log(sqrt(n)) complexity the sqrt(n) comes from traversing the blocks and the log(sqrt(n)) comes from looking up cnt[k].

    Of course what I said doesn't apply for the first and last block in each query (I calculate those naively)

    I hope that this was understandable if not please reply so I could elaborate further.

    :)

    → Ответить