Smallest subarrays
Practice
3.1 (24 votes)
Binary search
Algorithms
C++
Problem
52% Success 5300 Attempts 30 Points 5s Time Limit 1024MB Memory 1024 KB Max Code
You are given two arrays \(A\) and \(B\) of length \(N\).
For every index \(i\) in array \(A\), find the length of the smallest subarray starting from index \(i\) such that there exist at least \(B[i]\) elements with a value greater than or equal to \(A[i]\) in the subarray. If no such subarray exists, then print \(-1\).
Input format
- The first line contains an integer \(N\) denoting the number of elements in array \(A\) and \(B\).
- The second line contains space-separated integers denoting the array \(A\).
- The last line contains space-separated integers denoting the array.
Output format
Print \(N\) space-separated integers denoting the answer for every index in array \(A\).
Constraints
\(1 \le N \le 3 \times 10^5\)
\(1 \le A[i] \le 10^9\)
\(1 \le B[i] \le N\)
Explanation
- For index \(1\) , \(A[1] = 8\)
- For subarray \([8, 2, 4, 1, 9]\) , number of elements with value greater than equal to \(8\) is \(2\) which is less than or equal to \(B[1]\).
- For index \(2\) , \(A[2] = 2\)
- For subarray \([2, 4, 1, 9]\) , number of elements with value greater than equal to \(2\) is \(3\) which is less than or equal to \(B[2]\).
- For index \(3\) , \(A[3] = 4\)
- No such subarray exists, thus print \(-1\).
- For index \(4\) , \(A[4] = 1\)
- For subarray \([1]\) , number of elements with value greater than equal to \(1\) is \(1\) which is less than or equal to \(B[4]\)
- For index \(5\) , \(A[5] = 9\)
- For subarray \([9]\) , number of elements with value greater than equal to \(9\) is \(1\) which is less than or equal to \(B[5]\)
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Submissions
Please login to view your submissions
Similar Problems
Points:30
9 votes
Tags:
AlgorithmsBinary SearchMediumOpenSorting
Points:30
18 votes
Tags:
AlgorithmsBinary SearchMediumPrefix sumSearchingTwo pointerprefix-sum
Points:30
14 votes
Tags:
Ad-HocApprovedBinary SearchData StructuresMediumOpenSorting
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor