kitesho's blog

By kitesho, 10 months ago, In English

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 explanation

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 »

  • Vote: I like it
  • +3
  • Vote: I do not like it