ryuga222's blog

By ryuga222, history, 4 months ago, In English,

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

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

»
4 months 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).

»
4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    9 days 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.

    • »
      »
      »
      9 days 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.