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.
Полный текст и комментарии »
