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

Ответ

( 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

Ответ

( Narkhan Kamzabek )
комментарий/решение(6) олимпиада

Задача №3.

Задача C. Разделяем на пары

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Есть массив

$a$ из

$n$ целых чисел. Для каждого

$k$ от 1 до

$\lfloor \frac{n}{2} \rfloor$ , найдите

$k$ различных пар, что сумма абсолютных разностей пар была минимизирована. Более формально, выберите

$2k$ различных индексов, и разбейте их на

$k$ пар

$(i_1, j_1), (i_2, j_2), \dots, (i_k, j_k)$ , чтобы значение

$|a_{i_1} - a_{j_1}| + |a_{i_2} - a_{j_2}| + \dots + |a_{i_k} - a_{j_k}|$ было минимально.

Формат входного файла

В первой строке находятся одно целое число

$n$ (

$1 <= n <= 2*10^5$ ). Во второй строке находятся

$n$ целых чисел

$a_1, a_2,…, a_n (1 <= a_i <= 10^9)$ .

Формат выходного файла

Выведите

$\lfloor \frac{n}{2} \rfloor$ целых чисел, где

$k$ -е число является ответом

$k$ пар.

Система оценки

Данная задача содержит

$6$ подзадач, в которых выполняются следующие ограничения:

$n <= 11$ . Оценивается в $7$ баллов.
$n <= 18$ . Оценивается в $11$ баллов.
$n <= 500$ . Оценивается в $13$ баллов.
$n <= 5000$ . Оценивается в $15$ баллов.
$a_i <= 5000$ . Оценивается в $13$ баллов.
Исходные условия задачи. Оценивается в $41$ баллов.

Примеры:

Вход

6
1 3 5 8 13 21

Ответ

2 5 13

Вход

11
31 12 1 36 41 57 21 79 86 63 97

Ответ

5 11 18 27 39

( Narkhan Kamzabek )
комментарий/решение олимпиада

Задача №4.

Задача C. Восстановление строки

Ограничение по времени:

3 секунды

Ограничение по памяти:

256 мегабайт

Вам дана строка

$s$ длины

$n$ , состоящая из строчных латинских букв и символов `?'. Также, вам даны

$m$ условий. Каждое условие описывается тремя целыми числами

$l_1$ ,

$l_2$ и

$x$ , которые означают что подстрока

$(s_{l_1} \ldots s_{l_1+x-1})$ должна быть равна подстроке

$(s_{l_2} \ldots s_{l_2+x-1})$ . Вам нужно заменить каждый символ `?' на строчную латинскую букву так чтобы выполнялись все

$m$ условия. Среди всех таких строк, найдите лексикографически минимальную. Строка

$a$ лексикографический меньше строки

$b$ , если

либо первые $k$ символов этих строк совпадают, а $k + 1$ -й символ в $a$ алфавитном порядке идет раньше $k + 1$ -го символа строки $b$ . Например, $abcdef < abdaaaa$ , так как первые два символа совпадают, а третья буква первой строки( $c$ ) в алфавитном порядке идет раньше третьей буквы второй строки( $d$ ).
либо строка $a$ является префиксом строки $b$ . Например, $abc < abcde$ .

Формат входного файла

В первой строке находится одно целое число

$n(1 <= n <= 300000)$ . Во второй строке находится строка

$s$ , состоящая из

$n$ строчных латинских букв и символов `?'. В третьей строке находится одно целое число

$m(1 <= m <= 300000)$ . В следующих

$m$ строках записаны по три целых числа

$l_1$ ,

$l_2$ и

$x$

$(1 <= l_1, l_2 <= n - x + 1)$ , означающие что подстрока

$(s_{l_1} \ldots s_{l_1+x-1})$ равна подстроке

$(s_{l_2} \ldots s_{l_2+x-1})$ .

Формат выходного файла

Выведите лексикографически минимальную строку, которая удовлетворяет всем условиям, либо

$-1$ , если такой строки не существует.

Примеры:

Вход

10
a?b?b???b?
3
1 4 3
7 9 2
3 10 1

Ответ

abbabbbbbb

Вход

Ответ

-1

( Narkhan Kamzabek )
комментарий/решение(2) олимпиада

Задача №5.

Задача C. Марафон Канто

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Скоро лето, Есмахан решил, что пора начать бегать по утрам в своем городе Канто. Город Канто представляет собой

$n$ перекрестков соединённых

$n - 1$ дорогой, где от любого перекрестка можно добраться до любого другого перекрестка двигаясь по дорогам. В планах было начать бегать с воскресенья, однако в этот же день был назначен городской ежегодный веломарафон Канто. Определим маршрут

$(a,b)$ , что

$a < b$ , множеством дорог, которые лежат на кратчайшем пути между стартовым перекрестком

$a$ и конечным перекрестком

$b$ . Длиной маршрута

$(a,b)$ будем называть количество дорог по которым он проходит. Есмахан не хочет бегать по занятым дорогам веломарафона во время пробежки. На вход дается

$n$ количество перекрёстков в городе Канто. Далее дается

$n - 1$ дорога соединяющая два перекрестка. Гарантируется, что дается дороги таким образом, что от любого перекрестка можно добраться до любого другого перекрестка переходя только по дорогам. После дается

$q$ количество запросов на которые вы должны ответить. Запросы даются двух видов:

$x$ $y$ , в нем вы должны ответить длиной самого длинного маршрута если веломарафон будет проходить через маршрут $(x, y)$ .
$k$ , в нем должны ответить количеством различных маршрутов $(x, y)$ , что Есмахан выберет маршрут длиной $k$ .

Выведите ответ на каждый запрос. Поэтому хочет выяснить длину самого длинного маршрута

$(u, v)$ который будет проходить по свободным дорогам от веломарафона маршрутом

$(x, y)$ , чтобы его пробежка была максимальна. Так же, Есмахан хочет выяснить сколько возможных маршрутов

$(x, y)$ веломарафона возможно, что его пробежке будет длины

$k$ ?

Формат входного файла

Первая строка содержит одно целое число

$n$ (

$2 <= n <= 5*10^5$ ), обозначающее количество перекрестков в городе Канто. В каждой из следующих

$n-1$ строк содержится описание дорог: два целых числа

$u$ и

$v$

$(1 <= v,u <= n, u \ne v)$ . Следующая строка содержит одно целое число

$q$ (

$1 <= q <= 5*10^5$ ), обозначающее количество запросов. Следующие

$q$ строк содержат описания запросов. Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса:

$1$

$x$

$y$

$(1 <= x < y <= n)$ для запросов первого типа.

$2$

$k$

$(0 <= k <= n - 1$ ) для запросов второго типа.

Формат выходного файла

Для каждого запроса выведите ответ на него.

Система оценки

Данная задача содержит

$10$ подзадач, в которых выполняются следующие ограничения:

Примеры из условия. Оценивается в $0$ баллов.
$n <= 1000$ . Гарантируется, что $u_i=i$ , $v_i=i+1$ для всех $i$ ( $1 <= i < n$ ). Оценивается в $8$ баллов.
Гарантируется, что $u_i=i$ , $v_i=i+1$ для всех $i$ ( $1 <= i < n$ ). Оценивается в $10$ баллов.
$n, q <= 500$ . Оценивается в $9$ баллов.
$n, q <= 3000$ . Оценивается в $11$ баллов.
Гарантируется, что все запросы 1-типа и $x_i = 1$ для всех $i$ ( $1 <= i <= q$ ). Оценивается в $12$ баллов.
Гарантируется, что все запросы 1-типа. Оценивается в $12$ баллов.
$q <= 10$ . Оценивается в $11$ баллов.
$u_i=i+1, v_i=\lfloor \frac{i+1}{2} \rfloor$ для всех $i$ $(1 <= i < n$ ). Оценивается в $10$ баллов.
Исходные условия задачи. Оценивается в $17$ баллов.

Пример:

Вход

Ответ

Замечание

В первом запросе следущие четыре веломаршрута заставят Есмахана выбрать маршрут длины 3: (1, 3), (1, 5), (3, 6), (5, 6). Во втором запросе два самых длинных маршрутов длины 2: (2, 5) и (4, 8). В третьем запросе один самый длинный маршрут длины 2: (2, 5). В четвертом запросе следущие шесть веломаршрутов заставят Есмахана выбрать маршрут длины 4: (2, 4), (2, 7), (2, 8), (4, 7), (4, 8), (7, 8). В пятом запросе один самый длинный маршрут длинны 5: (6, 8). В шестом запросе ответ 12. ( Narkhan Kamzabek )
комментарий/решение олимпиада

Задача №6.

Задача F. Нархан и скобочки

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

256 мегабайт

Недавно на уроке информатики Нархан проходил скобочные последовательности. После этого он захотел придумать обозначение

$k$ -особенной скобочной последовательности. Давайте рассмотрим скобочную последовательность длины

$n$ , где $n$ - четное. Нархан сперва выбрал для каждого индекса особенная она или нет. Теперь он считает скобочную последовательность

$k$ -особенной, если на особенных индексах стоят ровно $k$ открывающихся скобок и сама последовательность является правильной скобочной последовательностью. Также он хочет определить красоту этой скобочной последовательности и для этого у него есть массив из

$n$ положительных целых чисел

$a_1, a_2, \dots a_n$ . Давайте выпишем все индексы

$k$ -особенной скобочной последовательности где стоят открывающиеся скобки, пусть это

$i_1, i_2, \dots, i_m$ . Тогда красотой этой последовательности для Нархана будет -

$a_{i_1} + a_{i_2} + \dots + a_{i_m}$ . Вам известны числа

$n$ и

$k$ , массив

$a_1, a_2, \dots a_n$ , а также какие позиции особенные. Помогите Нархану найти среди всех

$k$ -особенных скобочных последовательностей максимальную возможную красоту, так как эта задача для него является непосильной. Определение правильной скобочной последовательности смотрите в примечаниях.

Формат входного файла

Первая строка содержит два целых числа -

$n$ и

$k$ (

$2 <= n <= 2*10^5, 0 <= k <= n$ ) . Гарантируется, что

$n$ - четное. Во второй строке

$n$ целых числа

$a_1, \ldots, a_n$ (

$1 <= a_i <= 10^9$ ) - значения элементов массива. В третьей строке

$n$ чисел

$c_1, \ldots, c_n$

$(c_i = \{0, 1\})$ .

$c_i=1$ означает, что индекс

$i$ - особенный, иначе нет.

Формат выходного файла

Если нет ни одной

$k$ -особенной скобочной последовательности длины

$n$ выведите

$-1$ . Иначе выведите максимальную красоту среди всех

$k$ -особенных скобочных последовательностей

Примеры:

Вход

6 3
1 6 3 4 7 3
1 1 1 1 1 1

Ответ

Вход

6 0
1 2 3 4 5 6
1 0 0 0 0 0

Ответ

-1

Вход

8 3
7 9 12 5 6 6 8 9
0 1 1 0 1 1 1 0

Ответ

Замечание

Напомним, что такое правильная скобочная последовательность:

<<()>> — правильная скобочная последовательность;
если $s$ — правильная скобочная последовательность, то <<(>> + $s$ + <<)>> — правильная скобочная последовательность;
если $s$ и $t$ — правильные скобочные последовательности, то $s + t$ — правильная скобочная последовательность.

Например, <<()()>>, <<(())()>>, <<(())>> и <<()>> являются правильными скобочными последовательностями, а <<)(>>, <<()(>> и <<)))>> — нет. ( Narkhan Kamzabek )
комментарий/решение олимпиада