P11094 [ROI 2021] Cutting Trees (Day 2)

Translated from [ROI 2021 D2T3](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day2.pdf). The “2D” organization is responsible for issuing logging permits. They received logging requests along a road. There are $n$ trees along the road. The $i$-th tree grows at coordinate $x_i$ and has height $h_i$. The information about the trees is sorted, satisfying $x_1 < x_2 < \dots < x_{n-1} < x_n$. Trees can be cut one by one as follows: cut a tree and make it fall to the left or to the right. To prevent trees from being damaged while falling, it must not touch any uncut tree within a distance less than its own height. In other words, if the tree at coordinate $x_i$ with height $h_i$ falls to the right, then there must be no uncut tree at coordinate $x_j$ such that $x_i < x_j < x_i + h_i$. If the same tree falls to the left, then there must be no uncut tree at coordinate $x_j$ such that $x_i − h_i < x_j < x_i$. Next to the tree at the left boundary $x_1$ and the tree at the right boundary $x_n$, there are important buildings, so a fallen tree is not allowed to lie outside the interval $[x_1, x_n]$. In other words, if $x_i − h_i < x_1$, then the tree at coordinate $x_i$ with height $h_i$ cannot fall to the left; if $x_i + h_i > x_n$, then the tree at coordinate $x_i$ with height $h_i$ cannot fall to the right. The organization received $q$ logging requests. Each request consists of two numbers $l_i$ and $r_i$, meaning the applicant wants to cut trees from the $l_i$-th to the $r_i$-th (inclusive). While processing a request, it is only allowed to cut trees with indices from $l_i$ to $r_i$. The cut trees may fall into the area to the left of $l_i$ or to the right of $r_i$, but they must not go beyond $[x_1, x_n]$, and they must not touch any other trees outside the range from $l_i$ to $r_i$. For each request, compute the maximum number of trees that can be cut without damaging any tree. Each request should be processed independently (the trees are not actually cut).

The first line contains two integers $n$ and $q$. The next $n$ lines describe the trees. Each line contains two integers $x_i$ and $h_i$. It is guaranteed that $x_1 < x_2 < \dots < x_n$. Then follow the descriptions of $q$ logging requests, one per line. The $i$-th line contains two integers $l_i$ and $r_i$.

For each request, output the maximum number of trees that can be cut.

The last query of Sample 1 can be cut as follows:  For $100\%$ of the testdata, $1 \le n, q \le 500000,1 \le x_i, h_i \le 10^9,1 \le l_i \le r_i \le n$. | Subtask | Score | $n,q\le$ | | :----------: | :----------: | :----------: | | $1$ | $15$ | $100$ | | $2$ | $15$ | $500$ | | $3$ | $15$ | $5000$ | | $4$ | $5$ | $10000$ | | $5$ | $10$ | $100000$ | | $6$ | $10$ | $200000$ | | $7$ | $30$ | $500000$ | Translated by ChatGPT 5