Smallest subarrays

★★★★★

3.1

24 votes

Binary Search, Algorithms, C++

Details

Submissions

Discussion

Editorial

Problem

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$

Time Limit: 5

Memory Limit: 1024

Source Limit:

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]$