Refer this thread.

You can precompute for each element of the array, the segment that he is the maximum element, this can be done with a stack, finding the rightmost element which is greater than ai and its from 1 to i-1 for each i and then do the dame for the right, then in this interval, for each you need to find the smallest prefix sum un the range from ci to i (here ci is the rightmost element in the left which is greater than ai) and the maximum prefix sum from i to di (here di is the leftmost element in the right which is greater than ai), and the optimal range which its maximum is ai will be this range, the maximum and minimum prefix sums can be computed with segment tree in nlogn. Sorry for my poor english.

Well, maybe I can try. Let's fix an index i. We need find the minimum left index L and maximum right index R such that left maximum number in the range [L, R] be a[i]. How can we do this? Use binary search on index with range maximum query. Complexity for this would be O(n (log n)^2).
Then, at the particular index l in [L, i] and r in [i, R], such that the ans for the fixed i be maximum. Now, notice the following observation. l would be the index in [L, i] such that suffix sum till index l is maximum. Similarly, r would be in the range [i, R] such that prefix sum till r be the maximum. Now, we have to do range maximum query on prefix sum and suffix sum. Simple. Use segment tree once again. Complexity would be O(n log n).
Now, after we find the index l and r, now construct the ans. ans would be suff[l] — suff[i] + pref[r] — pref[i], it's easy to find out. So, it's given on yourself.
Now, we would do this for every i from 1 to n and update the answer.

Yeah bro, that's it. Final complexity is O(n (log n)^2).

I calculated prefix sum as well as suffix sum. Since array was immutable, so I created sparse table for array,prefix array and suffix array.

Then for each Index i, find the maximum subarray range that can be formed by applying binary search on sparse table of given array. After that find the maximum suffix sum in left part and maximum prefix sum in right side of that index. If the sum are positive add them.

Here is my solution for the above approach Solution

Let's find for some position "pos" L, R that in the interval from L to R the value in position pos is the largest, then you just need to find the maximum from pos to R and the minimum from L to pos. Now the answer can be MAX (pos, R) — MIN (L, pos) — a [pos], and therefore we iterate over all positions and perform these operations at each position

Давай найдем для какой то позиции "pos" L, R, что в интервале от L до R значение в позиции pos является наибольшим, тогда вам просто нужно найти максимум от pos до R и минимум от L до pos. Теперь ответ может быть MAX (pos, R) — MIN (L, pos) — a [pos], и поэтому мы перебираем все позиции и выполняем эти операции на каждой позиции

Best variable stores the minimum prefix sum that we have seen so far. In Kadane, at index i, the question is what is the maximum sum subarray that ends at index i. In other words, we want to find the maximum value of cur-pref where cur is the total sum of [0,i] and pref is some prefix sum of elements from [0,j] where j<i. So we want the minimum prefix sum we have seen so far in order to obtain the maximum value for cur-pref which is in our case cur-best. Then we also subtract mx as it will be removed.

other way to prove Other way to prove (x mod (ba)) mod a = x mod a since x mod (ba) = x - k*(ba) where k is some integer we can apply mod aon both sides

`(x mod (ba)) mod a = (x-k*(ba) mod a`
`(x mod (ba)) mod a = (x mod a - (k*b*a mod a)) mod a`
`(x mod (ba)) mod a = (x mod a - 0) mod a`
`(x mod (ba)) mod a = x mod a`

I used a ternary search for u can refer my solution 81858123. If u have any problem understanding do ask.

Using Binary Search

Maybe this explaination might help — https://pro-coder.tech/cf-1359-problems/

This might help!

https://mirror.codeforces.com/blog/entry/78116?#comment-632536

81792654 Have a look!

Try tracing an example. let's say h=10 c=5, try taking 1,2,3 and so on. if we take 1, the average would be 10, taking 2 the average would be 7.5, taking 3 the average would be 8.333 , taking 4 the average would be 7.5, notice that if you take any even number, the average would be the same. so in this example if 7.5 is the closest to t, we would surely take 2 because it is the minimum even number. Going on taking odd numbers you will notice that the average goes down towards 7.5 but never below it. That means that when you take larger odd numbers you would converge to the average when taking any even number(all gives the same average). Now as the average is always going down as we are taking larger odd numbers we can use binary search to know which is the optimal odd number that we should take to make the average as close as possible to t. Supposing that t is less than or equal to the average when taking an even number, the answer would be 2 because when taking odd numbers, the average would never cross the even average and if we assume that the average when taking an odd large number can ever reach the even average. we would still pick 2 becuase it is smaller than that odd number. so if t<=(h+c)/2.0 "the even average" , the answer would be 2 , else we know that t is greater than the even average. we also know that as the odd number goes to infinity the odd average converges to the even average, so if t is greater than the even average , we are sure that there exists an odd number that its average is as close as possible to t, so we do a binary search considering only odd numbers and calculate the average for that mid then checking if average>t then we want a smaller number so we discard the left half else we want a larger number so we discard the right half. Going on, we would get the number that gives the closest average possible to t. if anything is still not clear, feel free to ask.``

I don't see a single submission from your account for problem C. Please can you explain how did it took the soul out of you?

If i am not wrong you must be the kind of guy who creates new id just for the sake of posting comments.

check this video for detial explanation of problem c

https://youtu.be/Ts6to-_N-Y0

Yeah, brute force passes all the tests. I don't understand why the author's solution is so hard.

if(no_of_cards==1)
   ans=0;

It is not true. Here is the accepted submission.

Could you please elaborate it?

Is it replacing every $$$a \% b$$$ with $$$(a - (a / b) * b)$$$
My submission : 81937062

check this video editorials for c and d C : https://youtu.be/Ts6to-_N-Y0 D : https://youtu.be/1h1D7wMbDis

I will share the approach of one of my friend 81836011.

If we need to find the answer between L and R index, then we can do the following

Let i be the index of any maximum element in range L to R. There are three possiblities

1. The optimal subarray lies from L to i - 1
2. The optimal subarray lies from i + 1 to R
3. It include element at index i and therfore maximum of this subarray will be element at index i.

Now first two cases are recursion and for the third you need to find the maximum prefix sum for range i + 1 to R and maximum suffix sum for range L to i - 1. So these queries (maximum index, maximum suffix sum, maximum prefix sum) can be done by segment tree. The merging step will take O(logN) time and therefore even though our problem doesn't always reduce into two equal halves, we will achieve a time complexity of O(NlogN).

The values of $$$|t_b-t|$$$ are $$$1/499981$$$ and $$$1/499979$$$, for 499981 and 499979 number of cups respectively. The former is smaller.

$$$val1$$$ and $$$val2$$$ are only numerators, you have to compare $$$\frac{val1}{k}$$$ and $$$\frac{val2}{k+2}$$$

You haven't got the question right but don't worry.

The question asks for how many different arrays are stable where a stable array is one that gives the same remainder irrespective of the permutation of the array.

For instance, {1,2,3} and {1,3,2} are not two different stable arrays but two permutations of the array {1,2,3}. Notice how in the question it is mentioned that we have to find the arrays such that 1 <= a1 < a2 < a3 <...<an <= n. This is a strictly increasing array.

Please can you explain Problem D...i also can't able to under stand D.Although it looks straighforward

The values of $$$|t_b-t|$$$ are $$$1/499981$$$ and $$$1/499979$$$, for 499981 and 499979 number of cups respectively. The former is smaller.

what subarray are u referring to ?

case : -1 10 -20 1 5 Max sub array is 10 , u subtract 10 ans will be 0. But optimally it should be 1 5 , subtract 5 , u get 1. This happens because in sub array with maximum sum if the most contribution is from max element itself and later u will hv to remove it , we deviate from the ans .

You can choose subarray $$$3$$$ $$$2$$$ $$$2$$$ and $$$sum = 7$$$, $$$max = 3$$$, so $$$sum - max = 4$$$

It will lower the constant since you don't need to use % every time, which will make your program faster.

can we find ncr % 998242353 using DP(pascal's triangle).Because it am getting TLE

I see where your confusion comes from, but the problem clearly stated that:

"The water temperature in the barrel is an average of the temperatures of the poured cups."

I recommend that if you're not getting the correct answer in the test cases you re-read the problem (or the notes). This should've solved your doubt.