Soluție HackerRank pentru Number List, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Number List
- Domeniu: Combinatorics
- Limbaj: C++14
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
Cerință
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 ≤ T ≤ 10^5
1 ≤ N ≤ 2 × 10^5
1 ≤ A_i ≤ 10^9
0 ≤ K ≤ 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 sursă
//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;
}