images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
18/04/2024 18:28:25

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2261. Лучшее место

Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

32963.png
В зале ожидания на вокзале стоят `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 балла. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
loading