Falling Dominos

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).

C++: 2.5 seconds

Java, Python: 5 seconds

Memory Limit: 256mb

\(1 \leq x_i, h_i \leq 10^9\)

\(x_i < x_{i + 1}\) for all \(1 \leq i < n\)

The next \(n\) lines have two integers \(x_i\) and \(h_i\)

It is guaranteed that the positions of the dominos are distinct.

1 3

2 2

3 2

5 1

7 3

Credit: Eggag