HackerRank Combinatorics – Number List

Challenge: Number List

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464736389

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/number-list/problem

Cerinta

Sam is playing with an array, $A$, of $N$ positive integers. Sam writes a list, $S$, containing all $A$'s *[contiguous](https://en.wikipedia.org/wiki/Contiguity#Computer_science) subarrays*, and then replaces each subarray with its respective *maximum element*.

For example, consider the following $A$ where $N=3$:	
$A = \{1,2,3\}$		
Subarrays of $A$: $S_{initial} = \{ \{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,2,3\} \}$		
Updated (Maximum) Subarrays: $S_{maximums} = \{ \{1\}, \{2\}, \{3\}, \{2\}, \{3\}, \{3\} \}$

Help Sam determine how many numbers in $S_{maximums}$ are *greater than* $K$.

Input Format

The first line contains a single integer, $T$ (the number of test cases). Each test case is described over two lines:	
The first line of each test case contains two space-separated integers, $N$ (the number of elements in array $A$) and $K$, respectively.		
The second line of each test case contains $N$ space-separated integers describing the elements in $A$.  

**Constraints**  
$1 \le T \le 10^{5}$  
$1 \le N \le 2 \times 10^{5}$  
$1 \le A_i \le 10^{9}$  
$0 \le K \le 10^{9}$  
$The \ sum \ of \ N \ over \ all \ test \ cases \ does \ not \ exceed \ 10^{6}$.

Output Format

For each test case, print the number of $maximums \gt K$ in $S_{maximums}$ on a new line.

Cod sursa

//number-list.cpp
//Number List
//Weekly Challenges - Week 14
//Author: derekhh

#include<iostream>
using namespace std;

int a[200000];
int b[200000], nb;

int main()
{
	int t, n, k;
	cin >> t;
	while (t--)
	{
		cin >> n >> k;
		for (int i = 0; i < n; i++)
			cin >> a[i];
		int p = 0, cnt = 0, nb = 0;
		while (p < n)
		{
			if (a[p] <= k) cnt++;
			else
			{
				if (cnt != 0) b[nb++] = cnt;
				cnt = 0;
			}
			p++;
		}
		if (cnt != 0) b[nb++] = cnt;

		long long res = 0;
		for (int i = 0; i < nb; i++)
			res += (long long)(b[i] + 1) * b[i] / 2;
		res = (long long)n * (n + 1) / 2 - res;
		cout << res << endl;
	}
	return 0;
}