Dimash Tursynbai

Задача №1.

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

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

1 секунда

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

512 мегабайт

Легендарный <> Арлан дал следующую задачу своим фанатам: Вам даны два массива целых чисел $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

Ответ

Вход

2 1
1 1
1

Ответ

Замечание

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

Задача №2.

Задача B. MEXI

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

1.5 секунд

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

512 мегабайт

Аза решал следующию задачу от Нархана: Вам задан массив $a$, состоящий из $n$ целых неотрицательных чисел. Назовем разделение массива $a$ на $k$ отрезков $(l_1, r_1), \ldots, (l_k, r_k)$ $x$- хорошим, если выполняются следующие условия:

Каждый элемент массива $a$ принадлежит ровно одному отрезку.
Для каждого $1 <= i <= k$, $MEX$ чисел $(a_{l_i}, \ldots, a_{r_i})$ был меньше или равен $x$.

В этой задаче $MEX$ некоторого массива — это минимальное неотрицательное целое число, которое не содержится в этом массиве. Например:

$MEX$ для $[2,2,1]$ равен $0$, поскольку $0$ не принадлежит массиву.
$MEX$ для $[3,1,0,1]$ равен $2$, поскольку $0$ и $1$ принадлежат массиву, а $2$ — нет.
$MEX$ для $[0,3,1,2]$ равен $4$, поскольку $0$, $1$, $2$ и $3$ принадлежат массиву, а $4$ — нет.

Размером $x$ хорошего разделение является количество отрезков на которое оно было разделено — то есть $k$. Вам нужно для каждого целого числа $x$ от $0$ до $n-1$ вывести минимальный возможный размер $x$ хорошего разделения, если данное разделение невыполнимо выведите $-1$.

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

Первая строка содержит одно целое число — $n$ ($1 <= n <= 10^6$). Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ $(0 <= a_i <= 10^6)$ — массив $a$.

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

Выведите $n$ целых чисел, где $i$-е число — это минимальный возможный размер $x$ хорошего разделения при $x = i-1$, если данное разделение невыполнимо выведите $-1$.

Примеры:

Вход

4
0 1 0 2

Ответ

-1 3 2 1

Вход

1
2

Ответ

Замечание

В первом примере:

при $x = 0$, не существует хорошего разделения массива, поэтому выводим $-1$.
при $x = 1$, делим на $3$ отрезка: [$0$],[$1$],[$0,2$].
при $x = 2$, делим на $2$ отрезка: [$0,1$], [$0,2$].
при $x = 3$, один отрезок - сам массив [$0,1,0,2$].

( Dimash Tursynbai )
комментарий/решение(4) олимпиада