I want to know which is really more fast … printf() or fast…io… Maybe @l_returns can help :slight_smile:

Fast io is fast ( please use ‘\n’ instead of endl )

1 Like

why there are two main functions in setter’s soln


Tried. That didn’t help. Thanks anyway!
Btw disabling synchronization with stdio and untying input output streams (cin,cout) delivers same (if not better) performance than using scanf , printf (mostly).

Can anyone please help me with this code:: .
I have done exactly what was suggested in tutorial still i am unable to get 100. Please can anyone check the code.

1 Like

Your query same as @bufftowel
I helped him in solving that.

Check this thread.
Basically int tmp[k]={0} is causing TLE as it will be O(k) or more costly.

Thanks a lot. I have been stuck with this question since yesterday. You are a lifesaver​:heart::heart:.


Thanks for your kind words :slight_smile:

1 Like

I’m getting a TLE in this question. I have made all the necessary optimisations. Can anyone help me with it? Here is my code:

Can someone suggest optimizations in this code? Link

This problem can also be solved with segment tree of HashMap .
while building the segment tree store only those values in HashMap whose
frequency is greater than 1 in the whole array.
If an element has frequency 1 then it would not afffect any query.
My AC solution

1 Like

Isn’t the time limit 5 secs?
Subtask 13 of your solution takes 5.06…

Although I too solved this using the same technique, this only worked because testcases were weak.
Legitimate approach is by using sqrt decomposition only.

Same thoughts. I had the same idea. But did not submit thinking that testcases will be good :slight_smile:
Got fooled:p


Can anyone help me with this TLE :frowning:

Java has multiplier - 2x.

I dont get it how you work arround the division.
Somewhere you must devide the denominator, dont you?
But that is not possible since we deal with huge numbers, and MOD.
Can somebody explain?

How solve subtask3 using online varient MO’s algortihm??

1 Like


As far as I have understood from resource 2 for online Mo’s algorithm, the mentioned solution for this problem [100 pts.] is almost same, with the difference that block size is \sqrt n instead of n^{2/3}
Is it true ?

1 Like

Try with block size \le 350. Actually when the block size increases the cost of answering the query will also increase ``because we need to traverse the first and last block of current query and update the answer. So, naturally lesser block size means less number of iterations.

The tradeoff is in pre-calculation, as the number of blocks will increase [decrease block size], however, it doesn’t seem to affect much. Overall you get a speed up.

See these two solutions where you’ll notice the difference: TLE [\sqrt n block size], AC [BS = 300]

1 Like