I made a mistake while writing this problem, causing it to be much harder than originally intended. My flawed solution used simple recursion, but the actual solution requires segment trees. To fix this problem, I've made a new silver problem for this contest. Please solve that one instead.
Jayden is a little kid that likes to play video games. One of the games that he likes to play is Lumberjack, where the player, a lumberjack, must make a living by cutting down trees in a forest and selling them to a carpenter.
While playing the game, Jayden finds 
~N~ trees in the forest, all in a line. The 
~i^\text{th}~ tree will be at position 
~x_i~ on the line, with no tree sharing the same point. Since Jayden is a smart kid, he realizes that the trees will act like dominoes. When cutting a tree, it will fall to either the left or the right of the tree. If the tree has a height of 
~h_i~ and falls to the right, it will cause all trees located at positions 
~x_i+1~ to 
~x_i+h_i~, inclusive, to fall to the right as well. Similarly, if that tree falls to the left, all trees located at positions 
~x_i-h_i~ to 
~x_i-1~, inclusive, will also fall to the left.
For example, say that there are four trees of height 
~2~ at positions 
~1~, ~2~, 
~3~, and 
~5~. If Jayden cuts down the tree at position ~1~ and causes it to fall to the right, the second and third trees will also fall as a result. When the tree at position ~3~ falls, it causes the tree at position ~5~ to fall as well. By cutting down just one tree, the tree at position ~1~, Jayden can cause all of the trees in the line to fall.
Jayden can control the direction a tree falls when he cuts it. Given the line of trees he has found, what is the least amount of trees that Jayden has to cut in order to cause the entire line of trees to fall?
Input Specification
On the first line will be the integer ~N~ 
~(1 \le N \le 10^3)~. The next ~N~ lines will contain ~x_i~ and ~h_i~ 
~(1 \le x_i, h_i \le 10^8)~, two integers that describe the position and height of the ~i^\text{th}~ tree.
Output Specification
On a single line, print out the least amount of trees that Jayden has to cut down.
Sample Input
4
1 2
3 9
7 1
6 1
Sample Output
1
Comments
https://wcipeg.com/problem/domino
Do the test cases include cases such as:
input: 4 1 1 3 1 5 1 7 6
output: 1
My code cannot pass the case above and i get AC.
Not the same case, but two of my AC solutions give a different answer for
It should -- I remember having something similar as a case.