ryuga222's blog

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

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

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

Comments Comments (5)
| Write comment?
»
9 years ago, hide # |
 
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
»
9 years ago, hide # |
 
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