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) олимпиада