# PROBLEM LINK:

Div1, Div2Practice

**Author:**Praveen Dhinwa

**Tester:**Triveni Mahatha

**Editorialist:**Adarsh Kumar

# DIFFICULTY:

Easy-Medium# PREREQUISITES:

Binary search# PROBLEM:

You are given an array $A$ of $N$ positive integers. For all $i$, you need to find number of such $j (j e i)$ for which sum of number between $(i,j)$ (both exclusive) is less than or equal to $j^{th}$ element.# EXPLANATION:

I will try to explain the most straight forward solution that is easy to think at first.We will try to iterate over every minion j and try to find ranges of minion that will get voted by j^{th} minion. For i^{th} minion to get voted from j^{th} one following condition must be satisfied: A[j] \ge sum(i,j).

Let’s just solve for the case i>j. We can extend this one for the case i < j too using the similar argument. You can observe that right side of our condition is an increasing function while the left side is a constant. We can use binary search on i to find the break-point now. Now you just need to add 1 to the range (j+1, ext{last_valid_i}).

This problem reduces to offline range update and point query at every point. There are many possible ways of doing this. One of them uses DP with O(n) time complexity. I will describe that one in brief.

Say, you are given q updates (l_i,r_i), where in each update you need to add 1 to the range (l_i,r_i). Also, in the end you are required to report all the values of the array. A simple pseudocode for solving this task:

```
# arrays are initialized with zeroes
A[0...(N+1)] # Our oiginal array
for i=1...q:
A[r_i]+=1
A[l_i-1]-=1
for i=N...1:
A*+=A[i+1] # A* now contains the final value at ith position
```

# ALTERNATE SOLUTION

Even a solution that will look like a brute force at first sight is sufficient. Let's take a look at pseudocode:```
j = 1 to N:
i = j+1 to N:
if sum(i,j) > A[j]:
break
ans*+=1
i = j-1 to 1:
if sum(i,j) > A[j]:
break
ans*+=1
```

$ans*$ in the above pseudocode stores number of votes received by each minion. Time complexity of the above solution is $O(N.log(MAX))$. Proof is left as an exercise to reader.