Dimash Tursynbai

Есеп №1.

Есеп B. Бірегей есеп

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

1 second

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

512 megabytes

Аңыз адам <> Арлан өз жанкүйерлеріне келесі есепті ұсынды: Сізге мөлшері $n$ және $m$ болатын бүтін сандардан тұратын $a$ және $b$ массивтері берілген. $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.

Есеп В. MEXI

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

1.5 seconds

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

512 megabytes

Нархан Аза-ға келесі есепті ұсынды: Сізге мөлшері $n$ болатын бүтін сандардан тұратын $a$ массиві берілген. $a$ массивін $k$ бөлікке $(l_1, r_1), \ldots, (l_k, r_k)$ бөлуін $x$-жақсы бөлініс деп атаймыз егер келесі шарттар орындалса:

$a$ массивының кез-келген элементі дәл бір бөлікте жатады.
Кез келген $1 <= i <= k$ үшін, $(a_{l_i}, \ldots, a_{r_i})$ сандарының $MEX$і $x$-тен кіші немесе тең болады.

Осы есепте сандар жиынтығының $MEX$і — сол жиынтықта кездеспейтін ең кіші теріс емес бүтін сан. Мысалы:

$[2,2,1]$ $MEX$i $0$, себебі $0$ массивте кездеспейді.
$[3,1,0,1]$ $MEX$і $2$, себебі $0$ жәңе $1$ массивте кездеседі, ал $2$ — жоқ.
$[0,3,1,2]$ $MEX$і $4$, себебі $0$, $1$, $2$ жәңе $3$ массивте кездеседі, ал $4$ — жоқ.

$x$ жақсы бөліністің өлшемі деп қанша бөлікке бөлуін атаймыз, басқаша айтқанда $k$ саны. Әр бүтін $0$-ден $n-1$-ге дейінгі $x$ санына ең кішкентай мүмкін болатың $x$ жақсы бөліністің өлшемін шығарыңыз, егер сондай бөлініс болмаса $-1$ шыгарыңыз.

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

Бірінші жолда бір бүтін сан — $n$ ($1 <= n <= 10^6$) берілген. Екінші жолда $n$ бүтін сандар $a_1, a_2, \ldots, a_n$ $(0 <= a_i <= 10^6)$ — $a$ массиві берілген.

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

$n$ бүтін санды шығарыңыз, мұнда $i$-ші сан ол $x = i-1$ кездегі ең кішкентай мүмкін болатың $x$ жақсы бөліністің өлшемі. Олай бөлу мүмкін болмаса $-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) олимпиада