[Solution] 2^Sort Codeforces Solution | Codeforces Problem Solution 2022

[Solution] 2^Sort Codeforces Solution | Codeforces Problem Solution 2022

G. 2^Sort

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given an array a$a$ of length n$n$ and an integer k$k$, find the number of indices 1≤i≤n−k$1\le i\le n-k$ such that the subarray [ai,…,ai+k]$[a_i,\dots ,a_{i+k}]$ with length k+1$k+1$ (not with length k$k$) has the following property:

• If you multiply the first element by 20$2^0$, the second element by 21$2^1$, ..., and the (k+1$k+1$)-st element by 2k$2^k$, then this subarray is sorted in strictly increasing order.

More formally, count the number of indices 1≤i≤n−k$1\le i\le n-k$ such that

Input

The first line contains an integer t$t$ (1≤t≤1000$1\le t\le 1000$) — the number of test cases.

Solution Click Below:-  CLICK HERE

The first line of each test case contains two integers n$n$, k$k$ (3≤n≤2⋅105$3\le n\le 2\cdot {10}^5$, 1≤k<n$1\le k<n$) — the length of the array and the number of inequalities.

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$) — the elements of the array.

Marathon Codeforces Solution

2^Sort Codeforces Solution

All Distinct Codeforces Solution

Where's the Bishop? Codeforces Solution

The Clock Codeforces Solution

Binary Deque Codeforces Solution

3SUM Codeforces 

Gambling Codeforces Solution

The sum of n$n$ across all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output a single integer — the number of indices satisfying the condition in the statement.