Cerinta completa

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression:

In other words, if we let , then you need to calculate .

Given and queries, return a list of answers to each query.

Example

The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is .

The second query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is .

Return .

Function Description

Complete the solve function below.

solve has the following parameter(s):

  • int arr[n]: an array of integers
  • int queries[q]: the lengths of subarrays to query

Returns

  • int[q]: the answers to each query

Input Format

The first line consists of two space-separated integers, and .
The second line consists of space-separated integers, the elements of .
Each of the subsequent lines contains a single integer denoting the value of for that query.

Constraints

Sample Input 0

5 5
33 11 44 11 55
1
2
3
4
5

Sample Output 0

11
33
44
44
55

Explanation 0

For , the answer is

.
For , the answer is

.
For , the answer is

.
For , the answer is

.
For , the answer is

.

Sample Input 1

5 5
1 2 3 4 5
1
2
3
4
5

Sample Output 1

1
2
3
4
5

Explanation 1

For each query, the “prefix” has the least maximum value among the consecutive subsequences of the same size.

Limbajul de programare folosit: cpp14

Cod:

#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n, q;
    cin >> n >> q;
    int* a = new int[n];
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    
    deque<int> maxima;
    
    for (int i = 0; i < q; ++i)
    {
        int d;
        cin >> d;
        maxima.clear();
        
        int currentMax = 0;
        for (int j = d - 1; j >= 0; --j)
        {
            if (a[j] > currentMax)
                currentMax = a[j];
            maxima.push_front(currentMax);
        }
        int smallestMax = currentMax;
        int end = n - d;
        for (int j = 0; j < end; ++j)
        {
            maxima.pop_front();
            int next = a[j + d];
            for (deque<int>::reverse_iterator ri = maxima.rbegin();
                 ri != maxima.rend() && *ri < next; ++ri)
                *ri = next;
            maxima.push_back(next);
            if (maxima.front() != currentMax)
            {
                currentMax = maxima.front();
                if (currentMax < smallestMax)
                    smallestMax = currentMax;
            }
        }
        cout << smallestMax << endl;
    }
    
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464653220

Link challenge: https://www.hackerrank.com/challenges/queries-with-fixed-length/problem

Queries with Fixed Length