У вас есть робот, который двигается по числовой прямой. В момент времени $$$0$$$ он находится в точке $$$0$$$.
Вы посылаете роботу $$$n$$$ команд: в $$$t_i$$$-ю секунды вы указываете робот пойти в точку $$$x_i$$$. Когда робот получает команду, он сразу же начинает движение в сторону точки $$$x_i$$$ со скоростью $$$1$$$ в секунду и останавливается, когда достигает этой точки. Однако, когда робот двигается, он игнорирует все другие команды, которые он получает.
Например, предположим, что роботу приходят три команды: в секунду $$$1$$$ ехать в точку $$$5$$$, в секунду $$$3$$$ ехать в точку $$$0$$$ и в секунду $$$6$$$ ехать в точку $$$4$$$. Тогда робот будет стоять в $$$0$$$ до секунды $$$1$$$, затем начнет ехать к $$$5$$$, игнорируя вторую команду, достигнет $$$5$$$ в момент времени $$$6$$$ и сразу же начнет ехать к $$$4$$$, чтобы выполнить третью команду. В момент времени $$$7$$$ он доедет до $$$4$$$ и остановится там.
Команда $$$i$$$ считается выполненной успешно, если существует такой момент времени в отрезке $$$[t_i, t_{i + 1}]$$$ (то есть после того, как команда послана, и перед тем, как послана следующая, обе границы включительно; считаем $$$t_{n + 1} = +\infty$$$), что робот находится в позиции $$$x_i$$$. Посчитайте количество успешных команд. Обратите внимание, что проигнорированная команда все равно может быть успешной.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Затем следует описание наборов входных данных.
В первой строке набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество команд.
Затем $$$n$$$ строк описывают команды. В $$$i$$$-й из них записаны два целых числа $$$t_i$$$ и $$$x_i$$$ ($$$1 \le t_i \le 10^9$$$, $$$-10^9 \le x_i \le 10^9$$$) — время и точка назначения $$$i$$$-й команды.
Команды упорядочены по времени, то есть, $$$t_i < t_{i + 1}$$$ для всех возможных $$$i$$$.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество успешных команд.
8 3 1 5 3 0 6 4 3 1 5 2 4 10 -5 5 2 -5 3 1 4 1 5 1 6 1 4 3 3 5 -3 9 2 12 0 8 1 1 2 -6 7 2 8 3 12 -9 14 2 18 -1 23 9 5 1 -4 4 -7 6 -1 7 -3 8 -7 2 1 2 2 -2 6 3 10 5 5 8 0 12 -4 14 -7 19 -5
1 2 0 2 1 1 0 2
Движение робота в первом наборе входных данных описано в условии задачи. Только последняя команда успешна.
Во втором наборе входных данных вторая команда успешна: робот проходит через точку назначения $$$4$$$ в момент времени $$$5$$$. К тому же, последняя команда тоже в конце концов станет успешной.
В третьем наборе входных данных ни одна команда не успешна, и робот остановится в $$$-5$$$ в секунду $$$7$$$.
Вот $$$0$$$-индексированные последовательности позиций робота в каждую секунду для каждого набора входных данных из примера. Все отрезанные позиции совпадают с последней:
Название |
---|