Falling Dominoes

Given two array of integers A and B of size N.
Ai and Bi represents the position of a domino on x axis and its height.

For every Domino, You are required to find out out how many dominoes will fall if you pushes it to the right.
Consider that a domino falls if it is touched strictly above the base.
In other words, the fall of the domino with the initial coordinate Ai
and height Bi
leads to the fall of all dominoes on the segment [Ai, Ai+Bi-1].

Return an array of integer C of size N
such that
Ci: the number of dominoes that will fall
if you pushes the ith domino to the right (including the domino itself).

Note: All Ai are distinct.



Input Format

The argument given are two integer arrays A and B.

Output Format

Return an array of integers C.

Constraints

1 <= N <= 100000
-10^8 <= A[i] <= 10^8
2 <= B[i] <= 10^8

For Example

Input 1:
    A = [-13, 10, -16, 2] 
    B = [10, 7, 7, 11]
Output 1:
    C = [1, 1, 2, 2]

Input 2:
    A =  [-12, -6, -2, 3, -7, 13, -14, 19, -10, -18, 11] 
    B =  [6, 5, 10, 2, 3, 10, 5, 8, 6, 5, 9] 
Output 2:
    C = [6, 3, 2, 1, 4, 2, 7, 1, 5, 8, 3]
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Falling Dominoes on Interview Code Editor
Sign Up
to access hints and editorial solutions for Falling Dominoes

Discussion


Loading...
Click here to start solving coding interview questions