ГЖО 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 )
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.