images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
10/04/2025 23:19:50

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

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

printЗадачи

2799. Глобальное потепление

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

Из-за глобального потепления на планете Геликон начинает повышаться уровень океана. Математик Гэри Селдон пытается оценить возможный ущерб от затопления, чтобы доказать своё мастерство в предсказании будущего и отправиться в столицу Империи. Ущерб определяется тем, сколько жителей попадает в зону затопления. Жители проживают в городах, каждый из которых относится к одному из секторов. Город считается затопленным, если вода поднялась до уровня строго большего, чем высота этого города над уровнем моря. Требуется определить наиболее пострадавший сектор и количество людей в этом секторе, которых нужно эвакуировать из затопляемых городов. К сожалению, точный уровень повышения воды пока неизвестен, поэтому вычисления нужно произвести для каждой из возможных гипотез.

В первой строке ввода содержится три целых числа: количество секторов M (1≤M≤105), количество городов N (1≤N≤105) и количество гипотез об уровне поднятия воды Q (1≤Q≤105). Далее идет N строк, каждая из которых описывает один город и состоит из трех целых чисел: номер сектора mi, к которому город принадлежит (1≤mi≤M), количество жителей pi (1≤pi≤109), высота над уровнем моря hi (1≤hi≤109). Затем идет Q строк, каждая из которых содержит одно целое число – предполагаемый подъем уровня воды dj (1≤dj≤109).

Для каждой из Q гипотез выведите на отдельной строке два числа: номер наиболее пострадавшего сектора и количество людей, проживающих в затопляемых городах этого сектора. Если максимально пострадавших секторов несколько, выведите сектор с минимальным номером.

Пример ввода

2 3 3
1 70 60
1 1000 160
2 150 120
100
150
200

Пример вывода

1 70
2 150
1 1070

Пояснение к примеру:

  • В первом случае вода поднимется на 100 метров и затопит только первый город, относящийся к первому сектору.
  • Во втором случае вода поднимется на 150 метров и затопит по одному городу в секторах 1 и 2. Второй сектор пострадает больше, т.к. соответствующий город больше.
  • В третьем случае вода поднимется на 200 метров и затопит все города. Общее население сектора 1 больше, чем население сектора 2, поэтому он пострадает максимально.
loading