Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2261. Лучшее место
Бинарный поискСканирование, метод двух указателей
Олимпиадные задачи на русском языке
| 14/11/2015 | Муниципальный этап 9 класс (4) |
Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В зале ожидания на вокзале стоят `N` рядов из `M` кресел. Чтобы ожидающие не скучали, вместо некоторых кресел
установлено `K` мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они
смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит
на месте с номером `c` в ряде `r`, а `i`-й роутер расположен на месте `C_i` в ряде `R_i`, то расстояние до `i`-го
роутера вычисляется как `max(|r-R_i|,|c-C_i|)`, где `|x|` – абсолютное значение `x`. Креслам в зале ожидания
был присвоен приоритет от 1 до `N*M-K`, меньшие номера получили кресла с меньшим расстоянием до ближайшего
роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с
меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в
зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом).
Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.
Напишите программу, которая вычисляет расстояние до ближайшего роутера от кресла с некоторым заданным приоритетом.
Первая строка ввода содержит четыре целых чисел — количество рядов `N`
(`2\ ≤\ N\ ≤\ 10^9`) и мест в ряду `M` (`2\ ≤\ M\ ≤\ 10^9`), количество роутеров `K` (`1\ ≤\ K\ ≤\ 100`, `K\ <\ N*M`),
количество запросов `Q` (`1\ ≤\ Q\ ≤\ 100`). Далее следует `K` строк, содержащих два целых числа — местонахождение
роутеров: номер ряда `R_i` (`1\ ≤\ R_i\ ≤\ N`) и номер места в ряду `C_i` (`1\ ≤\ С_i\ ≤\ M`). Среди них
нет совпадающих. Далее следует строка, содержащая `Q` целых чисел в диапазоне от 1 до `N*M-K` – приоритеты кресел.
Вывести для каждого запроса на отдельной строке одно целое число — расстояние до ближайшего роутера от кресла с
заданным приоритетом.
Пример ввода
4 7 2 4 2 5 4 4 1 6 16 26
Пример вывода
1 1 2 3
Система оценки и описание подзадач
Подзадача 1 (40 баллов)
`2\ ≤\ N\ ≤\ 100`, `2\ ≤\ M\ ≤\ 100`, `1\ ≤\ K\ ≤\ 100`
В этой подзадаче 10 тестов, каждый тест оценивается в 4 балла. Баллы за каждый тест начисляются независимо.
Подзадача 2 (30 баллов)
`100\ <\ N\ ≤\ 1000`, `100\ <\ M\ ≤\ 1000`, `1\ ≤\ K\ ≤\ 100`
В этой подзадаче 10 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
Подзадача 3 (10 баллов)
`10^3\ <\ N\ ≤\ 10^9`, `10^3\ <\ M\ ≤\ 10^9`, `K=1`
В этой подзадаче 5 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.
Подзадача 4 (20 баллов)
`10^3\ <\ N\ ≤\ 10^9`, `10^3\ <\ M\ ≤\ 10^9`, `1\ <\ K\ ≤\ 100`
В этой подзадаче 10 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
