Задача №113824. Ваня и куртки
Ваня в очередной раз собрался изменить что-нибудь в своей жизни и решил начать с того, чтобы заранее составить график ношения курток в ближайшие n дней.
Он прочитал несколько учебных пособий по эксплуатации курток, поэтому он знает, что разные куртки предназначены для разных температурных диапазонов. Для каждой из своих m курток он определил l i и r i — минимальное и максимальное значение температуры, при которых допускается использование i -й куртки.
Ваня знает прогноз погоды на ближайшие n дней — так, в j -й день ожидается температура a j . Поскольку Ваня считает себя здравомыслящим человеком, то он будет одеваться по погоде, то есть в день j он может надеть любую куртку i , для которой l i ≤ a j ≤ r i . Помимо этого, Ваня считает себя модным и стильным, поэтому ни при каких обстоятельствах не наденет одну и ту же куртку два дня подряд.
Учитывая, что мама Вани не позволит ему выйти на улицу без куртки или сразу в нескольких куртках, составьте график их ношения на ближайшие n дней, удовлетворяющий всем пожеланиям Вани.
В первой строке входных данных записаны два числа n и m ( 1 ≤ n , m ≤ 100 000 ) — количество дней и число курток в гардеробе Вани соответственно.
Во второй строке записаны n чисел a i ( 0 ≤ a i ≤ 10 9 ) — температура в i -й день.
Затем следуют m строк, i -я из которых содержит два числа l i и r i ( 0 ≤ l i ≤ r i ≤ 10 9 ) — температурные ограничения на использование i -й куртки.
Все числа во входных данных целые.
Если существует способ подобрать куртку на каждый из n дней, то в первой строке выведите слово « Yes » (без кавычек), а во второй строке выведите n чисел b i — номер куртки, которую Ване следует надеть в i -й день. В противном случае в единственной строке выведите слово « No » (без кавычек). Куртки нумеруются с единицы в том порядке, в котором они даны во входных данных.
Если подходящих расписаний ношения курток несколько, разрешается вывести любое из них.
В первом примере, помимо ответа « 2 1 2 4 », правильным также является ответ « 1 2 1 4 ».
Во втором примере ответ отсутствует, так как Ване пришлось бы надеть первую куртку и в первый, и во второй день.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
4 4 25 25 30 50 10 40 20 30 70 100 50 50
Yes 1 2 1 4
4 2 30 40 50 60 30 40 50 60
No