K-th Maximum solution codechef

K-th Maximum solution codechef

You are given a sequence of integers A1,A2,,ANA1,A2,…,AN and an integer KK. Find the number of contiguous subsequences AL,AL+1,,ARAL,AL+1,…,AR such that RL+1KR−L+1≥K and the KK-th element of the subsequence (AL+K1AL+K−1) is equal to the maximum of all elements of the entire sequence.

Input Format K-th Maximum solution codechef

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers NN and KK.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, print a single line containing one integer — the number of contiguous subsequences satisfying the given conditions.

Constraints K-th Maximum solution codechef

  • 1T2001≤T≤200
  • 1KN21051≤K≤N≤2⋅105
  • |Ai|105|Ai|≤105 for each valid ii
  • the sum of NN over all test cases does not exceed 51055⋅105


Subtask #1 (10 points)

  • T10T≤10
  • N100N≤100

Subtask #2 (90 points) original constraints

Sample Input 1  K-th Maximum solution codechef 

5 3
1 2 3 4 5

Sample Output 1 


Explanation K-th Maximum solution codechef

Example case 1: (3,4,5)(3,4,5) is the only contiguous subsequence such that its 33-rd element is equal to the maximum of the whole sequence (which is 55).

Leave a Comment

Your email address will not be published.