Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Из-за глобального потепления на планете Геликон начинает повышаться уровень океана.
Математик Гэри Селдон пытается оценить возможный ущерб от затопления, чтобы доказать
своё мастерство в предсказании будущего и отправиться в столицу Империи. Ущерб определяется тем,
сколько жителей попадает в зону затопления. Жители проживают в городах, каждый из которых относится
к одному из секторов. Город считается затопленным, если вода поднялась до уровня строго большего,
чем высота этого города над уровнем моря. Требуется
определить наиболее пострадавший сектор и количество людей в этом секторе,
которых нужно эвакуировать из затопляемых городов.
К сожалению, точный уровень повышения воды пока
неизвестен, поэтому вычисления нужно произвести для каждой из возможных гипотез.
В первой строке ввода содержится три целых числа: количество секторов `M` (`1 <= M <= 10^5`),
количество городов `N` (`1 <= N <= 10^5`) и количество гипотез об уровне поднятия воды `Q` (`1 <= Q <= 10^5`).
Далее идет `N` строк, каждая из которых описывает один город и состоит из трех целых чисел: номер сектора `m_i`,
к которому город принадлежит (`1 <= m_i <= M`), количество жителей `p_i` (`1 <= p_i <= 10^9`),
высота над уровнем моря `h_i` (`1 <= h_i <= 10^9`).
Затем идет `Q` строк, каждая из которых содержит одно целое число -- предполагаемый
подъем уровня воды `d_j` (`1 <= d_j <= 10^9`).
Для каждой из `Q` гипотез выведите на отдельной строке два числа:
номер наиболее пострадавшего сектора и количество людей, проживающих в затопляемых городах этого сектора.
Если максимально пострадавших секторов несколько, выведите сектор с минимальным номером.
```sample Пример ввода
2 3 3
1 70 60
1 1000 160
2 150 120
100
150
200
```
```sample Пример вывода
1 70
2 150
1 1070
```
*Пояснение к примеру:*
* В первом случае вода поднимется на 100 метров и затопит только первый город, относящийся к первому сектору.
* Во втором случае вода поднимется на 150 метров и затопит по одному городу в секторах 1 и 2. Второй сектор пострадает больше, т.к. соответствующий город больше.
* В третьем случае вода поднимется на 200 метров и затопит все города. Общее население сектора 1 больше, чем население сектора 2, поэтому он пострадает максимально.
Начало
Рабочее место участника
Быстрая сортировка