Районная олимпиада по информатике. 2018-2019 учебный год. 8-11 классы


Задача H. Возрастающие подмассивы

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Вам дан массив $a$ длины $n$ и $q$ запросов. В каждом запросе вам даются два числа $l, r \ (1 \leq l \leq r \leq n)$, нужно разбить подмассив $a_l, a_{l+1}, \ldots, a_r$ на минимальное количество возрастающих подмассивов. Выведите это количество для каждого запроса.
Формат входного файла
Первая строка содержит два числа $n, q$ - размер массива и количество запросов. Во второй строке находятся $n$ чисел - массив $a \ (1 \leq a_i \leq 10^5)$. Следующие $q$ строк содержат два числа $l, r$ - описания запросов.
Формат выходного файла
Выведите $q$ строк - ответы на запросы.
Пример:
Вход
4 3
3 1 4 2
1 4
1 3
4 4
Ответ
3
2
1
Замечание
Подмассив $a_l, a_{l+1}, \ldots, a_r$ является возрастающим если для всех $l \leq i \leq r - 1$ выполняется условие $a_i < a_{i+1}$. $ \\ \\ $ Ответы на запросы в первом примере: $ \\ $ [3, 1, 4, 2] - [3], [1, 4], [2] $ \\ $ [3, 1, 4] - [3], [1, 4] $ \\ $ [4] - [4] $ \\ $ Подзадачи: $\\ 1 \leq n, q \leq 1000 - 40 \ баллов. \\ 1 \leq n, q \leq 10^5 - 60 \ баллов. \\$ ( Nurlybek Aimagambetov )
посмотреть в олимпиаде

Комментарий/решение:

  0
2018-12-14 12:25:25.0 #

AC

показать/скрыть код

  1
2019-01-08 23:04:11.0 #

показать/скрыть код

  0
2019-01-09 00:35:34.0 #

показать/скрыть код