ibrahimsherif's blog

By ibrahimsherif, history, 6 years ago, In English

http://acm.timus.ru/problem.aspx?space=1&num=1613

Hi, i am trying to solve this problem using SQRT decomposition but i am getting TLE, how can it be optimized more or is my approach wrong.

Here is my code: https://ideone.com/tnuvKA

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you got TLE because you were doing binary search on each block. You can speed it up by using MO's Algorithm + Compression.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I know MO's algorithm but don't really know the compression part ?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Did you notice that the count of different number of X is at most (N + Q) ? Nah, just compress it into smaller number.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        yeah i did and i think if i use map it would be the same problem like binary search so i need to count in an array. Right ?