АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

908. Покраска паттернов

Ограничение времени: 3 сек.
Ограничение памяти:131072 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Дана целочисленная последовательность a1a2, ..., aN и M паттернов вида (x, y, d). Будем говорить, что часть последовательности al, ..., ar покрывается паттерном (x, y, d), если:

·      rl + 1 = d;

·      al = x;

·      ar = y.

Найдите все элементы последовательности, которые покрыты хотя бы одним паттерном.

В первой строке входного файла записано целое число N (1  N  5∙104) — длина последовательности. Во второй строке через пробел записаны целые числа a1a2, ..., aN (−108  ai  108). В третьей строке записано целое число M (1  M ≤ 5∙104) — количество паттернов. В i-й из следующих M строк записаны три целых числа xiyidi, которые задают i-й паттерн (−108  xi, yi ≤ 108; 2 ≤ di ≤ 20).

В выходной файл выведите строку длины N, состоящую из нулей и единиц. На i-й позиции должна стоять единица, если элемент ai покрыт хотя бы одним паттерном и ноль в противном случае.

Пример

Поток ввода

Поток вывода

5

1 2 3 4 5

3

2 3 2

3 4 2

1 5 4

01110

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XIV Межвузовская олимпиада 2011 /
907. F - Опрос приборов 908. 909. H - Сотовая связь 910. I - Мaршрутизация 911. J - Взвешивание-2
 
время генерации 0.079 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.