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 мегабайт

int c = 0

for(int i = l...r)

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

print(c).

Это слишком медленно. Так что оптимизируйте это!

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

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

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