ГЖО 7-8 класс 2019 год


Задача D. Оптимизировать!

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

Дан массив $a$ длины $n$ ($a_1, a_2, ..., a_n$). И заданы $q$ запросов. Для каждого запроса задано $l, r$ ($1 <= l <= r <= n$). Вам дан псевдокод его решения, где число $c$ ответ на запрос:
int c = 0

for(int i = l...r)

  c = (c + a[i] + abs(c - a[i])) / 2

print(c).
Это слишком медленно. Так что оптимизируйте это!
Формат входного файла
В первой строке записано одно целое число $n$ ($1 <= n <= 10^6$) — длина массива. Во второй строке записано n целых чисел $a_1, a_2, ..., a_n$ ($1 <= |a_i| <= 10^9$) — сам массив. В третьей строке записано одно число $q$ ($1 <= q <= 10^6$) — количество запросов. В каждой из следующих $q$ строк записано по два целых числа $l$ и $r$ ($1 <= l <= r <= n$), описывающих один запрос.
Формат выходного файла
Найди $c$ для каждого запроса.
Пример:
Вход
10
1 6 3 88 2 9 45 78 23 6
5
1 3
4 5
6 10
5 7
2 7
Ответ
6
88
78
45
88
( Narkhan Kamzabek )
посмотреть в олимпиаде

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

  0
2019-12-19 12:19:33.0 #

FULL ACCEPTED:

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

пред. Правка 2   -2
2019-12-19 12:22:14.0 #

пред. Правка 2   0
2019-12-19 12:22:12.0 #

Задача решается максимумом на отрезке (Я решил деревом отрезков) за O(log n)

  2
2019-12-19 12:21:49.0 #

Zyma, еще такой коммент и будете забанены

  0
2020-04-14 20:47:34.0 #

Память позволяет написать спарс тейбл

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

пред. Правка 2   0
2022-01-18 11:13:45.0 #

DELETED