Specialty of a sequence

★★★★★

2.4

47 votes

Adhoc, Algorithms, Implementaion, Quick Sort, Sorting

Details

Submissions

Discussion

Editorial

Problem

You are given a sequence $A$ of length $n$ and a number $k$ . A number $A[l]$ is special if there exists a contiguous subarray that contains exactly $k$ numbers that are strictly greater than $A[l]$ . The specialty of a sequence is the sum of special numbers that are available in the sequence. Your task is to determine the specialty of the provided sequence.

Input format

First line: Two numbers $n$ and $k$
Second line: $n$ integers that represent the elements of the array

Constraints

$1 \leq k \leq n \leq 10^5$

$-10^9 \leq A[l] \leq 10^9$ for all array indices $l$

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

The beauty will be $4+3+2 = 9$ .

For $4$ , subsequence is $[4,3,2,7,8]$

For $3$ , subsequence is $[3,2,7,8]$

For $2$ , subsequence is $[2,7,8]$

For $7, 8$ there do not exist such subsequences.