Narkhan Kamzabek

Есеп №1.

Есеп D. Оңтайландыру!

Уақытка қойылған шектеу:

3 seconds

Жадқа қойылған шектеу:

512 megabytes

Ұзындығы $n$ болатын $a$ массивы берілген ($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$ жолда 2 бүтін сандар $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 seconds

Жадқа қойылған шектеу:

512 megabytes


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.

Есеп С. Жұптарға бөлеміз

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

1 second

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

256 megabytes

$n$ бүтін сандардан тұратын $a$ массиві бар. 1-ден $\lfloor \frac{n}{2} \rfloor$-дейінгі әр $k$ үшін, жұптардың абсолютті айырмашылықтарының қосындысы минимал болатын $k$ әр түрлі жұптарды табыңыз. Басқаша айтқанда, $ |a_{i_1} - a_{j_1}| + |a_{i_2} - a_{j_2}| + \dots + |a_{i_k} - a_{j_k}|$ мәні минимал болатын, $(i_1, j_1), (i_2, j_2), \dots, (i_k, 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. Cөзді табу

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

3 seconds

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

256 megabytes

Сізге ұзындығы $n$ болатын, кіші латын әріптері және `?' таңбаларынан тұратын $s$ сөзі беріледі. Сондай-ақ, сізде $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$ символ бірдей , ал $a$ның $k + 1$-ші символы алфавитте $b$ның $k + 1$-ші символын ерте болады. Мысалы, $abcdef < abdaaaa$, бірінші екі символдары бірдей, ал бірінші сөздің үшінші әрпі ('$c$') екінші сөздің үшінші әрпінен ('$d$') алфавитте ерте кездеседі.
немесе $a$ сөзі $b$ сөзінің префиксі. Мысалы, $abc < abcde$.

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

Бірінші жолда $n(1 <= n <= 300000)$ бүтін саны берілген. Екінші жолда ұзындығы $n$ болатын $s$ сөзі берілген. Үшінші жолда $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.

Есеп С. Канто марафоны

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

2 seconds

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

256 megabytes

Жаз келіп, Есмахан таңертең өзінің Канто қаласында жүгіретін уақыты келді деп шешті. Канто қаласы $n - 1$ жолдарымен байланысқан $n$ қиылыстарыдан тұрады. Мұнда кез-келген қиылыстан жолдар бойымен кез-келген басқа қиылысқа жетуге болады. Жоспар бойынша, жүгіру жексенбі күні басталуы керек еді, бірақ сол күні қалада жыл сайын өтетін Канто веломарафоны жоспарланған болатын. Біз $(a,b)$, маршрутын, $a$ бастапқы қиылысы мен $b$ соңғы қиылысы арасындағы жолдар жиынтығымен анықтаймыз, мұнда әрқашан $a < b$. $(a,b)$ маршрутының ұзындығы - ол өтетін жолдардың саны. Есмахан жүгіру кезінде веломарафонның маршрутымен қиылысқаның қаламайды. Сондықтан ол веломарофонмен қиылыспайтын, ең ұзын $(u, v)$ маршрутың білгісі келеді. Сондай-ақ, берілген $k$ санына, Есмахан қанша $ (x,y) $ веломарафонының маршрутың бар екенің білгісі келеді, егер ол тандаған маршруттың ұзындығы $k$ болса. Сізге Канто қаласындағы $n$, қиылыстар саны, берілген. Әрі қарай, екі қиылысты қосатын $ n - 1 $ жол беріледі. Кез-келген қиылыстан жолдар бойымен кез-келген басқа қиылысқа жетуге болады. Осыдан кейін $q$ сұраныстардың саны беріледі. Сұраныстардың екі түрі бар:

$x$ $y$, егер сіз веломарафон $(x,y) $ маршрутында өтсе, онда сіз ең ұзақ жолдың ұзындығын табуыңыз керек.
$k$, қанша $ (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$ баллға бағаланады.

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

Есеп №6.

ЕсепF. Нархан және жақшалар

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

1.5 seconds

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

256 megabytes

Нархан информатика сабағында жақшалар тізбегін өтті. Осыдан кейін, оған керемет ой келді: $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$-индекс ерекше екенін білдіреді, әйтпесе жоқ.

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

Ұзындығы $n$ болатын $k$-ерекше жақшалар тізбегі болмаса, $-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 )
комментарий/решение олимпиада