Narkhan Kamzabek


Задача №1. 

Задача 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 )
комментарий/решение(6) олимпиада
Задача №2. 

Задача 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 )
комментарий/решение(6) олимпиада