Как известно, Андрей Сергеевич –
ярый коллекционер бабочек. Он имеет огромную коллекцию, экспонаты которой
собраны со всего мира. Будем считать, что в мире существует 2 * 109 видов
бабочек.
Чтобы не запутаться, Андрей
Сергеевич присвоил каждому виду уникальный номер. Нумерация бабочек всегда
начинается с единицы. Теперь он хочет знать, есть ли бабочка с видом k в
его коллекции, или же её придётся добывать, затрачивая уйму сил и денег.
Вход. В первой строке содержится
количество видов бабочек n (1 ≤ n ≤ 105) в коллекции Андрея Сергеевича. В следующей
строке находятся n упорядоченных по возрастанию чисел – номера видов
бабочек в коллекции. Все виды бабочек в коллекции имеют различные номера.
В третьей строке записано
количество видов бабочек m (1 ≤ m ≤ 105), про которых Андрей Сергеевич хочет узнать,
есть ли они у него в коллекции или же нет. В последней строке содержатся m
чисел – номера видов бабочек, наличие которых необходимо проверить.
Выход. Выведите m строк. Для
каждого запроса выведите “YES”, если бабочка с данным номером содержится в коллекции, и “NO” в противном случае.
|
Пример
входа |
Пример
выхода |
|
7 10 47 50 63 89 90 99 4 84 33 10 82 |
NO NO YES NO |
структуры
данных – set
Номера видов бабочек в коллекции будем хранить во множестве s. Тогда проверка того, что бабочка вида x имеется у Андрея Сергеевича, сводится к проверке принадлежности числа x множеству s.
Номера видов бабочек в коллекции храним во множестве s.
set<int> s;
Читаем входные
данные.
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &x);
s.insert(x);
}
Обрабатываем m запросов.
scanf("%d", &m);
for (i = 0; i < m; i++)
{
Проверяем, имеется ли в коллекции бабочка вида x. Ответ утвердительный, если число x содержится во
множестве s.
scanf("%d", &x);
if (s.find(x) != s.end()) puts("YES");
else puts("NO");
}