В
Все
Б
Биология
Б
Беларуская мова
У
Українська мова
А
Алгебра
Р
Русский язык
О
ОБЖ
И
История
Ф
Физика
Қ
Қазақ тiлi
О
Окружающий мир
Э
Экономика
Н
Немецкий язык
Х
Химия
П
Право
П
Психология
Д
Другие предметы
Л
Литература
Г
География
Ф
Французский язык
М
Математика
М
Музыка
А
Английский язык
М
МХК
У
Українська література
И
Информатика
О
Обществознание
Г
Геометрия
228778anonim228778
228778anonim228778
28.11.2022 21:26 •  Информатика

Новый маршрут для трекинга Сейчас самое время планировать новые трекинговые маршруты.

Опишем холмистую местность массивом из n чисел. Высота i-го холма равна hi. Маршрут должен идти по k подряд идущим холмам (учитывая тот холм, с которого маршрут будет начинаться). Немолодым туристам не очень нравится, когда приходится много раз подниматься в гору — переходить с более низкого холма на более высокий.

туристам определиться с выбором маршрута — напишите программу, которая отвечает на запросы о количестве переходов с более низкого холма на более высокий на данном маршруте.

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

В первой строке даны натуральные числа n, m (2≤n,m≤2⋅105) — общее количество холмов и количество запросов соответственно.

Во второй строке даны n целых чисел hi(1≤hi≤105) — высоты холмов.

В следующих m строках записаны пары чисел lj и rj (1≤li≤rj≤n) — запросы на количество переходов с более низкого холма на более высокий на маршруте с началом в холме lj и завершением в rj.

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

Выведите m чисел — ответы на запросы.

Примеры
Ввод
Вывод
2 3
2 37
1 2
2 2
1 1
1
0
0
Ограничения
Время выполнения: 3 секунды

Показать ответ
Ответ:
nactya201613
nactya201613
25.08.2021 11:32

n,m = map(int,input().split())

A = list(map(int,input().split()))

C = [0]*n

for i in range(1,n):

   if A[i]>A[i-1]:

       C[i] += C[i-1]+1

   else:

       C[i]=C[i-1]

for i in range(m):

   l,r = map(int,input().split())

   print(C[r-1]-C[l-1])

0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота