ryuga222's blog

TLE in mo's algo
By ryuga222, history, 7 years ago, In English

Can anyone check my solution Id. 34415408. I don't know why it is giving TLE. Code link : http://mirror.codeforces.com/contest/86/submission/34415408

  • Vote: I like it
  • -8
  • Vote: I do not like it

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

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

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

First of all notice that this is an old problem. So your execution time will be multiplied by 2.

There are many optimizations that you can do —

  1. Honestly use scanf/printf for IO.
  2. You are using too much long long variables, it takes too much time. Use only when necessary.
  3. You are using long long BLOCK = 512, if you use const long long compiler will optimize division / modulo for with the number.
  4. In the compare function, you are calculating the block number there, again and again. The division is a costly operator. You can pre-calculate the block number in main function and just use that.
  5. You are accessing the cnt[] array 5 times in add/remove function. But it is possible to design those by accessing only twice or even once.
  6. Silly optimization — if anywhere you have i++, and changing it to ++i doesn't affect much. Then use ++i. Somehow ++i is more faster.

So, it is reasonable that you got TLE.

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

    damn... it worked when i optimized the add/remove function. Can't believe it was giving TLE. Thanks a lot :D.

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

    how i can pre-calculate the BLOCK in main function?? i don't understand that.

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

      Take another array blc[], and precalculate like blc[i] = i / block_size;, then use this array in compare function.

      → Reply