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

Задача . E. Прокачка персонажа


Задача

Темы: Бинарный поиск Перебор Структуры данных реализация разделяй и властвуй *2200

Монокарп играет в компьютерную игру. Он начинает игру, будучи \(1\) уровня. Ему предстоит сразиться с \(n\) монстрами в порядке от \(1\) до \(n\). Уровень \(i\)-го из них равен \(a_i\).

Когда Монокарп встречает очередного монстра, происходит следующее:

  • если уровень Монокарпа строго выше уровня монстра, то монстр спасается бегством;
  • иначе Монокарп сражается с монстром.

После каждого \(k\)-го сражения с монстром (сбежавшие монстры не считаются) уровень Монокарпа увеличивается на \(1\). То есть, после \(k\) сражений с монстрами уровень становится равен \(2\), после \(2k\) — равен \(3\), после \(3k\) — равен \(4\) и так далее.

Требуется обработать \(q\) запросов следующего вида:

  • \(i~x\): будет ли Монокарп сражаться с \(i\)-м монстром (или же этот монстр сбежит), если параметр \(k\) равен \(x\)?
Входные данные

В первой строке записаны два целых числа \(n\) и \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) — количество монстров и количество запросов.

Во второй строке записаны \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 2 \cdot 10^5\)) — уровни монстров.

В \(j\)-й из следующих \(q\) строк записаны два целых числа \(i\) и \(x\) (\(1 \le i, x \le n\)) — номер монстра и количество сражений, необходимых для повышения уровня в \(j\)-м запросе.

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

На каждый запрос выведите «YES», если Монокарп сразится с \(i\)-м монстром в этом запросе, и «NO», если \(i\)-й монстр сбежит.


Примеры
№Входные данныеВыходные данные
1 
4 16
2 1 2 1
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4
 
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
2 
7 15
1 1 2 1 1 1 1
5 3
2 2
2 2
1 6
5 1
5 5
7 7
3 5
7 4
4 3
2 5
1 2
5 6
4 1
6 1
 
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO

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

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

Ваш ответ

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


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

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