Есеп 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$, $i \neq j$ болса $p_i \neq p_j$) беріледі. Мәреге бірінші болып $p_1$ келді, екінші болып $p_2$, \ldots, соңғы болып $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. Бірегей есеп

Аңыз адам <> Арлан өз жанкүйерлеріне келесі есепті ұсынды: Сізге мөлшері $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

Ответ

1

Вход

2 1
1 1
1

Ответ

0

Замечание

Бірінші мысалды жалғыз әдіс бар, ол — $(1, 2)$ және $(3, 4)$ бөліктеріне бөлу.

Есеп C. Cөзді табу

Сізге ұзындығы $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

Вход

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$ болсын. Студенттер арасында $(a_1, b_1), \ldots, (a_m, b_m)$ деген дәл $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$).

Есеп С. Үштік

Сізге ұзындығы $n$ болатын $a$ атаулы сандар тізбегі және $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