Задача A. Спортивные программисты

Ассоциация спортивных программистов Казахстана решила организовать забег перед Олимпиадой. В забеге приняло участие $N$ человек. На старте бегуны расположились друг за другом в линию в порядке от $1$ до $N$. Когда был дан свисток, участники забега ринулись с мест, при этом поддерживая порядок кто за кем бежит. Участник с номером $1$ бежит первым, а участник с номером $N$ — последним. Но какой же это забег, если никто никого не обгоняет? Обгон происходит, когда у одного из участников развязываются шнурки на кроссовках. Пока бегун завязывает свои шнурки, следующие за ним участники могут его обогнать. Рассмотрим на примере. При $N = 5$ изначальная линия бегунов выглядит так: $1$ $2$ $3$ $4$ $5$. В процессе у участника с номером $2$ развязываются шнурки. Пока он их завязывает, предположим, что двоим участникам удается его обогнать. Тогда порядок участников становится: $1$ $3$ $4$ $2$ $5$. Если теперь у бегуна с номером $4$ возникнут проблемы со шнурками, из-за чего он пропустит, например, одного человека вперед, то линия станет: $1$ $3$ $2$ $4$ $5$. Вам дается $N$ и порядок в котором бегуны финишировали. Вам необходимо узнать минимальное количество участников, у которых могли развязаться шнурки во время забега. В первой строке находится одно целое число $N(1 <= N <= 200000)$. Во второй строке находятся $N$ целых чисел $p_1, p_2, \ldots, p_N$($1 <= p_i <= N$, $p_i \neq p_j$ если $i \neq j$) — первым финишировал бегун $p_1$, вторым был $p_2$, \dots, последним — $p_N$. Выведите одно целое число — ответ на задачу. Вход

6
1 2 5 4 3 6

Ответ

2

Вход

3
1 2 3

Ответ

0

Разберем первый пример. Изначальная линия: $1$ $2$ $3$ $4$ $5$ $6$. Один из возможных вариантов событий: Сначала развязался шнурок у бегуна с номером $4$ и его обогнал $5$-й. Линия стала равной $1$ $2$ $3$ $5$ $4$ $6$. После этого развязался шнурок у бегуна с номером $3$ и его обогнали бегуны $5$ и $4$. Линия стала равной $1$ $2$ $5$ $4$ $3$ $6$. Можно показать, что если бы шнурки развязались у менее чем двух бегунов, тогда невозможно было бы получить нужный порядок.

Задача B. Уникальная задача

Легендарный <> Арлан дал следующую задачу своим фанатам: Вам даны два массива целых чисел $a$ и $b$ размера $n$ и $m$, соответственно. Все элементы массива $b$ попарно различны. Вам нужно найти количество способов разделить массив $a$ на $m$ отрезков $(l_1, r_1), \ldots, (l_m, r_m)$ так, чтобы выполнялись следующие условия:

• Каждый элемент массива $a$ принадлежит ровно одному отрезку.
• Для каждого $1 <= i <= m$, число $b_i$ встречается ровно один раз среди чисел $(a_{l_i}, \ldots, a_{r_i})$ (отрезки нумеруются по возрастанию левой границы).

Так как ответ может быть слишком большим, выведите его остаток при делении на $998244353$.

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

Первая строка содержит из два целых числа — $n$ и $m$ ($1 <= n, m <= 5 \cdot 10^5$). Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ $(1 <= a_i <= 5 \cdot 10^5)$ — массив $a$. Третья строка содержит $m$ целых чисел $b_1, b_2, \ldots, b_m$ $(1 <= b_i <= 5 \cdot 10^5)$ — массив $b$.

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

Выведите одно целое число — ответ на задачу Арлана по модулю $998244353$.

Примеры:

Вход

4 2
1 7 7 3
7 3

Ответ

1

Вход

2 1
1 1
1

Ответ

0

Замечание

В первом примере можно разделить массив на отрезки $(1, 2)$ и $(3, 4)$.

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

Вам дана строка $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

Вход

6
a????b
5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1

Ответ

-1

Задача A. Работать или отдыхать?

У Ади есть $S$ тенге. В каждый из следующих $N$ дней он решил, что будет либо целый день работать, либо целый день отдыхать. Он высчитал, что если будет работать в $i$-й день, то заработает $a_i$ тенге. А чтобы отдохнуть в $i$-й день, он потратит $b_i$ тенге. Другими словами, если в $i$-й день он будет работать, то количество его денег увеличиться на $a_i$, а если будет отдыхать, то количество денег уменьшится на $b_i$. Какое максимальное количество дней он может отдохнуть? При этом, ни в какой момент времени количество его денег не должно быть отрицательным. В первой строке находятся два целых числа $N$ и $S$($1 <= N <= 200000$, $0 <= S <= 10^9$) — количество дней и изначальное количество денег. В следующих $N$ строках находятся по два целых числа $a_i$ и $b_i(0 <= a_i,b_i <= 10^9)$. Выведите одно целое число — максимальное количество дней, в которые Ади может отдохнуть. Вход

3 5
1 4
1 3
2 3

Ответ

2

Вход

5 12
0 5
0 4
0 7
0 4
0 4

Ответ

3

В первом примере: в первый день он будет работать, а второй и третий день отдыхать. Во втором примере: он будет отдыхать в дни $2$, $4$ и $5$.

Задача B. Друзья

В HS учатся $n$ студентов включая Руслана. Для удобства пронумеруем всех студентов целыми числами от $1$ до $n$, а у Руслана всегда номер $1$. Известно, что среди студентов есть ровно $m$ пар друзей $(a_1, b_1), \ldots, (a_m, b_m)$. Пара $(a_i, b_i)$ означает что студенты под номерами $a_i$ и $b_i$ являются друзьями. Недавно Руслан открыл свой кружок по спортивному программированию. Теперь ему нужно пригласить туда как можно больше студентов. По вполне логичным причинам, Руслан сперва начнет приглашать своих друзей. Затем его друзья смогут пригласить своих друзей, а они — своих друзей и так далее. Однако не все так просто! У каждого студента в HS есть свой навык убеждения $c_i$. Также определим навык убеждения кружка как сумму навыков убеждений каждого отдельного члена кружка. Изначально навык убеждения кружка равен навыку убеждения Руслана: значению $c_1$. Нового студента можно пригласить в кружок только тогда, когда навык убеждения кружка не меньше навыка убеждения этого студента. Более формально, в любой момент времени любой участник кружка может позвать в кружок своего друга, при условии что сумма навыков убеждений всех членов кружка не меньше навыка убеждения этого друга. Разрешено набирать в кружок новых студентов до тех пор, пока это возможно.

Какое максимальное количество студентов Руслан сможет набрать к себе в кружок (включая самого Руслана)? В первой строке входного файла даны два целых числа $n$ и $m$ — количество студентов в HS и количество пар друзей ($2 <= n <= 2 \cdot 10^5$, $0 <= m <= 2 \cdot 10^5$). В следующих $m$ строках содержатся пары $(a_i, b_i)$, обозначающие пары друзей среди студентов. ($1 <= a_i, b_i <= n$, $a_i \neq b_i$) В последней строке содержатся $n$ целых чисел $c_1, \ldots, c_n$ — навыки убеждения каждого из студентов. ($1 <= c_i <= 10^9$) Гарантируется, что никакая пара студентов не встречается в списке друзей дважды. Выведите одно целое число — максимальное количество студентов которых Руслан сможет набрать к себе в кружок. Вход

7 6
1 2
3 1
1 4
5 3
4 5
6 7
2 2 1 12 5 3 6

Ответ

4

Вход

5 4
1 2
1 3
1 4
1 5
4 18 6 16 4

Ответ

3

Вход

2 0
1 1

Ответ

1

Разберем первый пример.

• Изначально Руслан один в секции. Навык убеждения кружка равен $c_1 = 2$. Руслан может пригласить в кружок друзей $2$ и $3$, но не может пригласить друга $4$, поскольку его навык убеждения $c_4 = 12 > 2$.
• Теперь в секции Руслана есть студенты $1$, $2$ и $3$. Навык убеждения кружка равен $c_1 + c_2 + c_3 = 2 + 2 + 1 = 5$. Студент номер $3$ может пригласить своего друга $5$ ($c_5 = 5 <= 5$). По прежнему пригласить студента $4$ не удается ($c_4 = 12 > 5$).
• Теперь в секции Руслана есть студенты $1$, $2$, $3$ и $5$. Навык убеждения кружка равен $c_1 + c_2 + c_3 + c_5 = 2 + 2 + 1 + 5 = 10$. Однако больше никаких студентов позвать в кружок невозможно. Студенты $6$ и $7$ не являются друзьями студентов в секции, а у студента $4$ по прежнему навык убеждения больше ($c_4 = 12 > 10$).

Задача C. Тройка

Вам дана последовательность чисел $a$ длины $n$ и $q$ запросов. Каждый запрос состоит из двух чисел $l$ и $r$. Для каждого запроса найдите следующие значение: $$ \sum_{i=l}^{r} \sum_{j=l}^{r} \sum_{k=l}^{r} max(a_i, a_j, a_k) - min(a_i, a_j, a_k) $$ Так как ответ может быть большим, выведите его по модулю $10^9 + 7$. В первой строке даны два целых числа $n$ и $q$ $(1 <= n, q <= 10^5)$. В следующей строке даны $n$ целых чисел $a_1, a_2, \ldots a_n$ $(1 <= a_i <= 10^9)$ — последовательность чисел. В следующих $q$ строках даны по два целых числа $l_i, r_i$ $(1 <= l_i <= r_i <= n)$ — описание $i$-го запроса. Выведите $q$ целых чисел — ответы на все запросы. Вход

5 5
1 2 3 4 5
1 5
1 3
2 5
2 3
4 4

Ответ

300
36
120
6
0

Вход

6 1
999370245 75 860 26427 218288294 917
1 6

Ответ

731295209