I believe it was because there was a codechef starters at the same time. I also remember the cc admin saying "we are discussing the clashing of the dates with codeforces".

problems*

So, this was said sarcastically?

You got downvotes for your previous comments

Problem D is actually even easier, you don't need any range data structures.

If you have $$$k$$$ open APs which together add a sum $$$s$$$ to some position $$$i$$$, when moving to $$$i - 1$$$, it will add a sum $$$s - (k - start_{i})$$$ where $$$start_{i}$$$ is the number of APs which start at $$$i$$$.

So by just storing the number of APs starting from a point (which can be trivially set when we add a new A), we have all the information we need to just simply solve it with a single iteration.

Submission — 153184495

How can you solve D with this technique from Polynomial Queries? I have an AC on CSES and honestly, I don't know how to use it here

Why ??

Don't forget A — cringe ;)

and cringe E (indeed)

I thought it was a segment tree problem, but my implementation was too buggy to finish it in contest time :(.

It can be done with a segment tree. For a range you should store the number of components in it and the connectivity information among its six vertical border cells. These are enough to merge two adjacent ranges.

What's the solution? i tried using binary search initially to find minimum required days

You can do the operations greedily from right to left.

Create a from the end.

collecting smaller elements in one array, and bigger elements in another array, because |ai — aj| must be minimum

Yeah i saw my friend doing it that way !

Just a bfs problem using reverse edges

Hints :

• 32768 is 2^15

• Max Probable Operation : 15

We can put the number of operations needed to make each number $$$i$$$, $$$1\text{ to }32768$$$ by using the second operation, $$$(2\times i)\text{ mod }32768$$$, in an array, $$$ans[\text{ }]$$$ . Then calculate if there is any number $$$j$$$ such that $$$j-i$$$ $$$+ans[j] $$$ $$$ \lt $$$ $$$ans[i]$$$.If there is then print $$$\text{MIN}(j-i + ans[j],\text{ 32768}-i)$$$ otherwise $$$\text{MIN}(ans[i],\text{ 32768}-i)$$$.

Try to make the height of all trees be 3

Water the tree with height 2 on day 1 so you can do something on the even days.

On day 1 , water the tree of height 2 , so new array becomes => [ 1 , 1 , 1 , 1 , 1 , 1 , 3] ,On day 2 , water the tree of height 1 , so new array becomes => [ 3 , 1 , 1 , 1 , 1 , 1 , 3] ,On day 3 , water the tree of height 1 , so new array becomes => [ 3 , 2 , 1 , 1 , 1 , 1 , 3] ,On day 4 , water the tree of height 1 , so new array becomes => [ 3 , 2 , 3 , 1 , 1 , 1 , 3] ,On day 5 , water the tree of height 2 , so new array becomes => [ 3 , 3 , 3 , 1 , 1 , 1 , 3] ,On day 6 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 1 , 1 , 3] ,On day 7 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 2 , 1 , 3] ,On day 8 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 2 , 3 , 3] ,On day 9 , water the tree of height 2 , so new array becomes => [ 3 , 3 , 3 , 3 , 3 , 3 , 3]

Someone please say how to solve 3rd case in 1st test case in 16 days as well.

Thank you for your replies Bungmint, robostac, helios_

They didn't say we always have to make everything equal to max element of array. Just extra check for max_element + 1 would have passed all testcase . I got this intution by this example which i created during contest Hope it help you.

Testcase Example — 1 1 1 1 1 1 1 1 1 2 (Instead making everything 2 make everything 3) Making everything 2 will cost 17 days while making 3 will cost 13 days . I was so happy when i found it during contest and got Ac.

memset is o(n) and you do it t times