Falling Dominos

D. Falling Dominos

No Submission Yet

Problem Statement

Tiger is bored in Health class so he is playing with \(n\) dominos arranged in a straight line — the \(i\)-th domino has position \(x_i\) and height \(h_i\). Tiger is clumsy (unless he is only pretending to be) so he wondered, for each \(i\) \((1 \leq i \leq n)\), how many dominos would fall if he were to knock over the \(i\)-th domino?

Note that Tiger is knocking over the dominos to the right, and if the \(i\)-th domino has been knocked over, it will knock over the \(j\)-th domino if \(x_i < x_j\) and \(x_i + h_i \geq x_j\) (and the \(j\)-th domino will fall to the same side as the \(i\)-th domino).

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb


\(1 \leq n \leq 2 \cdot 10^5\)
\(1 \leq x_i, h_i \leq 10^9\)
\(x_i < x_{i + 1}\) for all \(1 \leq i < n\)

Input Format

The first line has one integer \(n\)
The next \(n\) lines have two integers \(x_i\) and \(h_i\)
It is guaranteed that the positions of the dominos are distinct.

Output Format

Output \(n\) integers. For each \(i\) \((1 \leq i \leq n)\) output the number of dominos that would fall if Tiger knocked over the \(i\)-th domino.

Sample Input

1 3
2 2
3 2
5 1
7 3

Sample Output

4 3 2 1 1

Sample Explanation

If you knock over the second domino, it reaches the third domino at \(x = 3\), which then knocks over the fourth domino at \(x = 5\). Thus the total number is \(3\)

Credit: Eggag

Contact Us
LIT Discord Server