Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Удачная фотосессия
Феликс большой специалист в области фотографии. Особенно удачно у него выходят фотографии деревьев. Феликс отыскал в своем любимом городе аллею, вдоль которой друг за другом растут N деревьев. Для удобства он пронумеровал все деревья по порядку от 1 до N. Феликс может сделать фотографию, на которой изображено некоторое количество растущих подряд деревьев. Однако не каждая фотография деревьев может получиться удачной. По опыту Феликс знает, что фотография будет идеальной, если первое дерево, попавшее в кадр, имеет высоту X, второе – высоту X+1, третье – X+2 и так далее, где X это значение светосилы объектива фотоаппарата. Так как Феликс сам собрал свой фотоаппарат, он может подкрутить в нём гайки и поменять значение светосилы в любой момент. 

Фотографии Феликса не всегда выходят идеальными, поэтому он решил оценивать удачность фотографии, как количество деревьев, которые имеют ровно такую высоту, какую должны иметь деревья на идеальной фотографии. Например, фотографируя деревья с высотами 3, 2 и 5 метров и светосилой объектива равной 3, Феликс получит фотографию с удачностью 2, так как первое и последнее деревья имеют высоту 3 и 5, а высота второго дерева не равна 4.



Феликс уже оценил высоту каждого дерева вдоль аллеи и знает, что дерево с номером i имеет высоту Ai метров. Он хочет сделать M фотографий деревьев так, чтобы на j-ю из них попали все деревья с номерами от Lj до Rj включительно, а светосила объектива была равна Xj. Однако, до того как приступить, ему очень хочется знать, насколько удачной будет фотосессия, а именно какова удачность каждой отдельной фотографии. Помогите Феликсу определить эти значения.
Входные данные:
Первая строка входного файла содержит два целых числа, разделенных пробелом, N, M (1 ≤ N, M ≤ 105) – количество деревьев вдоль аллеи и количество фотографий, которые Феликс планирует сделать. 

Во второй строке находятся N целых чисел Ai (1 ≤ Ai ≤ 109), разделенных одиночными пробелами, – высоты деревьев.

В следующих M строках файла записаны по 3 целых числа Lj, Rj, Xj (1 ≤ Lj ≤ Rj ≤ N, 1 ≤ Xj ≤ 109) – параметры j-й по счету фотографии
Выходные данные:
Выходной файл должен содержать ровно M строк, в каждой из которых записано одно целое число Ansj – удачность j-й фотографии.

Примеры:
input.txt output.txt
1 5 3
1 3 2 5 6
2 4 3
2 4 1
1 5 2
2
1
3

Сложность задачи: 100%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи
Разбор примера.
На первую фотографию попадают деревья с высотами 3, 2 и 5. При светосиле объектива равной 3, первое и третье деревья имеют высоту, соответствующую идеальной фотографии. 

Вторая захватывает те же деревья, что и первая, но со светосилой 1. Только у второго дерева высота совпадает с высотой на идеальной фотографии. 

На третью фотографию попадают все деревья, второе, четвертое и пятое деревья имеют высоту, соответствующую идеальной фотографии для светосилы равной 2.
Показать обсуждение


На сайте гостей 17, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]