You are given an array A of size N. For each prefix of the A, you have to calculate the value described in the below function.
int func(){
int ans = 0;
for(int i = 0; i <= prefix_index; i++){
int c = 0;
for(int j = 0; j <= prefix_index; j++){
if(A[j] >= A[i]) c++;
}
ans = max(c * A[i], ans);
}
return ans;
}
i.e., in a prefix, the value for the index i is, number of elements greater than or equal to A[i] * A[i]. The answer for the prefix is maximum of these values. The output is a list of N numbers (one for each prefix).
constraints:
1 <= N <= 150000
1 <= A[i] <= 1e9
sample test case:
A = [10, 11, 12, 10, 11, 50, 70]
ans: [10, 20, 30, 40, 50, 60, 100]
test case explanationfor prefix 1 to 1number of values greater than or equal to 10 is 1. so value here is 10 * 1 = 10
The max value is 10.
for prefix 1 to 2number of values greater than or equal to 10 is 2. value = 10 * 2 = 20
number of values greater than of equal to 11 is 1. value = 11 * 1 = 11
The max value is 20.
for prefix 1 to 3number of values greater than or equal to 10 is 3. value = 10 * 3 = 30
number of values greater than of equal to 11 is 2. value = 11 * 2 = 22
number of values greater than of equal to 12 is 1. value = 12 * 1 = 12
The max value is 30.
for prefix 1 to 4number of values greater than or equal to 10 is 4. value = 10 * 4 = 40
number of values greater than of equal to 11 is 2. value = 11 * 2 = 22
number of values greater than of equal to 12 is 1. value = 12 * 1 = 12
number of values greater than or equal to 10 is 4. value = 10 * 4 = 40
The max value is 40.
for prefix 1 to 5number of values greater than or equal to 10 is 5. value = 10 * 5 = 50
number of values greater than of equal to 11 is 3. value = 11 * 3 = 33
number of values greater than of equal to 12 is 1. value = 12 * 1 = 12
number of values greater than or equal to 10 is 5. value = 10 * 5 = 50
number of values greater than or equal to 11 is 3. value = 11 * 3 = 33
The max value is 50.
for prefix 1 to 6number of values greater than or equal to 10 is 6. value = 10 * 6 = 60
number of values greater than of equal to 11 is 4. value = 11 * 4 = 44
number of values greater than of equal to 12 is 2. value = 12 * 2 = 24
number of values greater than or equal to 10 is 6. value = 10 * 6 = 60
number of values greater than or equal to 11 is 4. value = 11 * 4 = 44
number of values greater than or equal to 50 is 1. value = 50 * 1 = 50
The max value is 60.
for prefix 1 to 7number of values greater than or equal to 10 is 7. value = 10 * 7 = 70
number of values greater than of equal to 11 is 5. value = 11 * 5 = 55
number of values greater than of equal to 12 is 3. value = 12 * 3 = 36
number of values greater than or equal to 10 is 7. value = 10 * 7 = 70
number of values greater than or equal to 11 is 5. value = 11 * 5 = 55
number of values greater than or equal to 50 is 2. value = 50 * 2 = 100
number of values greater than or equal to 70 is 1. value = 70 * 1 = 70
The max value is 100.
I believe this can be solved using segment tree. Solutions without using segment tree will be also interesting. But want to know how to solve using segment tree.
Full text and comments »
