K-th Maximum Problem Code: KMAX2 Codechef Solution

 

 K-th Maximum Problem Code: KMAX2

Submit

Read problem statements in Mandarin, Russian, and Vietnamese as well.

You are given a sequence of integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ and an integer K$K$. Find the number of contiguous subsequences AL,AL+1,…,AR$A_L,A_{L+1},\dots ,A_R$ such that R−L+1≥K$R-L+1\ge K$ and the K$K$-th element of the subsequence (AL+K−1$A_{L+K-1}$) is equal to the maximum of all elements of the entire sequence.

Input Format

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two space-separated integers N$N$ and K$K$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output Format

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

Constraints

• 1≤T≤200$1\le T\le 200$
• 1≤K≤N≤2⋅105$1\le K\le N\le 2\cdot {10}^5$
• |Ai|≤105$|A_i|\le {10}^5$ for each valid i$i$
• the sum of N$N$ over all test cases does not exceed 5⋅105$5\cdot {10}^5$

Subtasks

Subtask #1 (10 points)

• T≤10$T\le 10$
• N≤100$N\le 100$

Subtask #2 (90 points) original constraints

Sample Input 1 

1
5 3
1 2 3 4 5

Sample Output 1 

1

Explanation

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

Author:5★janmansh

Date Added:24-08-2021

Time Limit:0.5 secs

Source Limit:50000 Bytes

Languages:CPP14, C, JAVA, PYTH 3.6, CPP17, PYTH, PYP3, CS2, ADA, PYPY, TEXT, PAS fpc, NODEJS, RUBY, PHP, GO, HASK, TCL, PERL, SCALA, LUA, kotlin, BASH, JS, LISP sbcl, rust, PAS gpc, BF, CLOJ, R, D, CAML, FORT, ASM, swift, FS, WSPC, LISP clisp, SQL, SCM guile, PERL6, ERL, CLPS, ICK, NICE, PRLG, ICON, COB, SCM chicken, PIKE, SCM qobi, ST, SQLQ, NEM

Solution in C++

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main(){

ll t,n,k,i;

cin>>t;

while(t--){

cin>>n>>k;

k--;

vector<ll>v(n);

ll mx=INT_MIN;

map<ll,ll>mp;

for(i=0; i<n; i++){

cin>>v[i];

mx = max(mx, v[i]);

}

ll c=0;

for(i=0; i<n; i++){

ll x = i+k;

//cout<<x<<" "<<v[x]<<"\n";

if(x<n && v[x]==mx){

//cout<<x<<" <== \n";

c+=(n-x);

}

}

cout<<c<<"\n";

}

}