Kotlin Heroes: Episode 10 |
---|
Закончено |
Рассмотрим отрезок координатной прямой от $$$1$$$ до $$$n$$$. На этом отрезке стоят $$$k$$$ смотровых башен.
У каждой башни есть два параметра — координата $$$x_i$$$ и высота $$$h_i$$$. Все координаты башен различны. С башни $$$i$$$ можно увидеть точку $$$j$$$, если $$$|x_i - j| \le h_i$$$ (где $$$|a|$$$ — это абсолютное значение $$$a$$$).
За одну монету можно увеличить высоту любой башни на $$$1$$$. Увеличивать высоту каждой башни можно произвольное число раз (в том числе и ноль раз).
Надо обработать $$$q$$$ независимых запросов. В $$$i$$$-м запросе задаются две различных точки $$$l$$$ и $$$r$$$. Надо посчитать минимально необходимое количество монет, чтобы можно было увидеть обе эти точки (с одной башни или с разных башен).
В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — длина отрезка координатной прямой и количество смотровых башен.
Во второй строке записаны $$$k$$$ целых чисел $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le n$$$) — координаты смотровых башен. Все координаты башен различны.
В третьей строке записаны $$$k$$$ целых чисел $$$h_1, h_2, \dots, h_k$$$ ($$$0 \le h_i \le n$$$) — высоты смотровых башен.
В четвертой строке записано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.
В каждой из следующих $$$q$$$ строк записаны два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$) — описание очередного запроса.
На каждый запрос выведите одно целое число — минимально необходимое количество монет, чтобы можно было увидеть обе точки (с одной башни или с разных башен).
20 32 15 106 2 031 2010 113 4
3 1 0
10 22 91 234 55 61 10
2 2 0
Название |
---|