Олимпиадный тренинг

Задача . A. Медвежонок и отображаемые друзья


Задача

Темы: реализация *1200

Полярный медвежонок Лимак любит переписываться с другими медведями в социальных сетях. Всего у него n друзей и уровень дружбы с i-м другом описывается целым числом ti. Чем больше это значение, тем сильнее дружат два медвежонка. Известно, что все ti различны.

Приближается весна и медведи начинают просыпаться. Лимак проснулся самым первым и сразу зашёл в любимую социальную сеть. Все его друзья ещё спят и пока что находятся оффлайн. В ближайшие часы некоторые из них проснуться и тоже сразу зайдут в социальную сеть.

В системе в специальном окне отображаются те из друзей, кто сейчас находится в сети, но не более чем k медведей. Если онлайн находится больше чем k, то из них показываются k самых близких друзей (то есть с наибольшими значениями ti).

Необходимо обрабатывать запросы двух типов:

  • «1 id» — друг с номером id заходит в социальную сеть. Гарантируется, что до этого он не был онлайн.
  • «2 id» — проверить, отображается ли друг с номером id в специальном окне. Вывести «YES» или «NO».

Как вы помните, Лимак ещё очень маленький, поэтому ему требуется ваша помощь в обработке запросов.

Входные данные

В первой строке входных данных записаны три числа n, k и q (1 ≤ n, q ≤ 150 000, 1 ≤ k ≤ min(6, n)) — количество друзей, размер специального окна для отображения друзей онлайн и количество запросов соответственно.

Во второй строке записаны n целых чисел t1, t2, ..., tn (1 ≤ ti ≤ 109), i-е из которых показывает уровень дружбы Лимака с другом номер i.

В i-й из последующих q строк записаны два целых числа typei и idi (1 ≤ typei ≤ 2, 1 ≤ idi ≤ n) — параметры i-го запроса. Если typei = 1, то данный запрос означает, что друг idi зашёл в социальную сеть. Если же typei = 2, то требуется проверить, отображается ли друг idi в специальном окошке.

Гарантируется, что все запросы первого типа содержат различные idi и что во входных данных присутствует хотя бы один запрос второго типа.

Выходные данные

Для каждого запроса второго типа выведите «YES» (без кавычек), если соответствующий друг присутствует в этот момент в специальном окне, и «NO» (без кавычек), если не присутствует.

Примечание

В первом примере у Лимака 4 друга, которые все изначально спят. В начале никто из друзей не показывается в специальном окне.

Поступают следующие 8 запросов:

  1. «1 3» — друг номер 3 заходит в сеть.
  2. «2 4» — требуется проверить, отображается ли друг 4. Он ещё не заходил онлайн, поэтому ответ «NO».
  3. «2 3» — требуется проверить, отображается ли друг 3. Он единственный из друзей сейчас онлайн, поэтому точно отображается в специальном окне. Печатаем ответ «YES».
  4. «1 1» — друг номер 1 заходит в социальную сеть. Сейчас в специальном окне показываются и друг 1 и друг 3.
  5. «1 2» — друг 2 заходит онлайн. Сейчас в сети уже целых три друга, но k = 2, поэтому только двое будут отображаться в специальном окне. Поскольку t1 < t2 и t1 < t3, то отображаться будут друзья 2 и 3.
  6. «2 1» — выводим «NO».
  7. «2 2» — выводим «YES».
  8. «2 3» — выводим «YES».

Примеры
№Входные данныеВыходные данные
1 4 2 8
300 950 500 200
1 3
2 4
2 3
1 1
1 2
2 1
2 2
2 3 
NO
YES
NO
YES
YES
2 6 3 9
50 20 51 17 99 24
1 3
1 4
1 5
1 2
2 4
2 2
1 1
2 4
2 3 
NO
YES
NO
YES

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w642
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет