1650. Миллиардеры @ Timus Online Judge

ENG RUS | Timus Online Judge |

Online Judge | Задачи | Авторы | Соревнования
--- | --- | --- | ---

О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки

Архив задач
Отправить на проверку
Состояние проверки
Руководство

Регистрация
Исправить данные
Рейтинг авторов

Текущее соревнование
Расписание
Прошедшие соревнования
Правила

## 1650. Миллиардеры

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Возможно, вы знаете, что из всех городов мира больше всего миллиардеров живёт в Москве. Но, поскольку работа миллиардера подразумевает частые перемещения по всему свету, в определённые дни какой-то другой город может занимать первую строчку в таком рейтинге. Ваши приятели из ФСБ, ФБР, MI5 и Шин Бет скинули вам списки перемещений всех миллиардеров за последнее время. Ваш работодатель просит посчитать, сколько дней в течение этого периода каждый из городов мира был первым по общей сумме денег миллиардеров, находящихся в нём.

### Исходные данные

В первой строке записано число n — количество миллиардеров (1 ≤ n ≤ 10000). Каждая из следующих n строк содержит данные на определённого человека: его имя, название города, где он находился в первый день данного периода, и размер состояния. В следующей строке записаны два числа: m — количество дней, о которых есть данные (1 ≤ m ≤ 50000), k — количество зарегистрированных перемещений миллиардеров (0 ≤ k ≤ 50000). Следующие k строк содержат список перемещений в формате: номер дня (от 1 до m − 1), имя человека, название города назначения. Вы можете считать, что миллиардеры путешествуют не чаще одного раза в день, и что они отбывают поздно вечером и прибывают в город назначения рано утром следующего дня. Список упорядочен по возрастанию номера дня. Все имена и названия городов состоят не более чем из 20 латинских букв, регистр букв имеет значение. Состояния миллиардеров лежат в пределах от 1 до 100 миллиардов.

### Результат

В каждой строке должно содержаться название города и, через пробел, количество дней, в течение которых этот город лидировал по общему состоянию миллиардеров, находящихся в нём. Если таких дней не было, пропустите этот город. Города должны быть отсортированы по алфавиту (используйте обычный порядок символов: ABC...Zabc...z).

### Пример

исходные данные | результат
--- | ---

    5
    Abramovich London 15000000000
    Deripaska Moscow 10000000000
    Potanin Moscow 5000000000
    Berezovsky London 2500000000
    Khodorkovsky Chita 1000000000
    25 9
    1 Abramovich Anadyr
    5 Potanin Courchevel
    10 Abramovich Moscow
    11 Abramovich London
    11 Deripaska StPetersburg
    15 Potanin Norilsk
    20 Berezovsky Tbilisi
    21 Potanin StPetersburg
    22 Berezovsky London

    Anadyr 5
    London 14
    Moscow 1

Автор задачи: Павел Атнашев
Источник задачи: NEERC 2008, Четвертьфинал Восточного подрегиона
Метки: структуры данных (скрыть метки для нерешенных задач)
Сложность: 569 Версия для печати Отправить на проверку Обсуждение на форуме (11)
Мои попытки Все попытки (4929) Все успешные попытки (1176) Рейтинг решений (450)