Есеп A. Тікенді кірпілер

Бүтін сандар түзуінде $n$ кірпі орналасқан. Әр кірпіде өзіңнің $x_i$ координатасы бар және олар өз қалауынша түзу бойында қозғала алады. Бірақ, өкінішке орай, кірпілерге алысқа баруға болмайды, сондықтан қозғалу кезінде олардың координасы $1$ мен $n$ арасындағы бүтін санда болуы керек. Сонымен қатар, әр кірпінің өзіндік қозғалыс жылдамдығы бар, атап айтқанда $i$-ге көршілес тұрған нүктеге өту $t_i$ секунд алады. Кірпілер өте тікенді тіршілік иелері, сондықтан кірпі онымен бір нүктеде басқа кірпі болғанын қаламайды. Кірпілердің бәрін қанағаттандыру үшін ең аз уақыт қажет екенін табыңыз. Бірінші жолда $n$ ($1 <= n <= 10^5$) — кірпілер саны бар. Келесі $n$ жолда кірпілер туралы ақпарат берілген. $i$-жолда екі $x_i$ ($1 <= x_i <= n$) және $t_i$ ($0 <= t_i <= 10^9$) — $i$-ші кірпінің орны және $i$-шы кірпінің көршілес нүктеге өтуге қажетті уақыты берілген. Жалғыз санды шығарыңыз — барлық кірпілерді қанағаттандыруға кететін ең аз уақыт. Вход

3
2 1
2 2
2 3

Ответ

2

Вход

6
4 1
4 7
1 9
3 0
5 11
2 14

Ответ

1

Бірінші мысалда бірінші кірпі нөмері $1$ші нүктеге барады(оған $1$ секунд кетеді), екінші кірпі $3$ші нүктеге(оған $2$ секунд), ал үшінші өз орнында $2$ қалады. Екінші мысалда бірінші кірпі $3$ке барады(осыған $1$ секунд), төртінші $6$ға барады($0$ секунд), ал қалғандары өз орнында қалады.

Есеп B. Платформер ойыны

Жақында Нархан өзінің жеке платформер ойынын құрастырды. Ұқсас жанрдағы көптеген ойындар секілді ойынның барлық әрекеттері екі өлшемді кеңістікте өтеді. Ойын әлемін $(0, 0)$ және $(m, 10^9)$ нүктелерін қосатын тіктөртбұрыш ретінде сипаттауға болады. Ойындағы барлық нысандар осы тіктөртбұрыштың ішінде орналасқан. $y=0$ түзуі жер болып саналады. Ойында қалыпты ауырлық күші әсер етеді. Ойыншы ойынды $(0, 0)$ нүктесінен бастайды және жеңіс үшін $(m, 0)$ нүктесіне жету керек. Ойында $n$ кедергі бар. Әр кедергіні тіктөртбұрыш ретінде сипаттауға болады. Барлық кедергілер жерге тікелей тиіп тұр. Олардың әрқайсысының орны үш $L_i$, $R_i$ және $H_i$ сандарымен сипатталады: тіктөртбұрыштың сол жақ ұшының $x$ координатасы, оң жақ ұшының $x$ координатасы және биіктігі. Кедергілер бір-бірімен қиылыспайды, бірақ бір-біріне жанасып тұруы мүмкін. Оған қоса, ешқандай кедергі бастапқы $(0, 0)$ және соңғы $(m, 0)$ нүктелерін кіргізбейді. Ойыншы солға немесе оңға еркін қозғала алады. Дегенмен ойыншы кедергілерді тесіп немесе оларды аттап өте алмайды. Бірақ ойыншы кедергілердің қабырғаларымен көтеріліп, түсе алады. Ойыншының әр қозғалысына дәл бір секунд кетеді. Нархан осы ойынды Аманболдан өтуді сұрады. Аманбол болса өте жалқау, сондықтан ол ойынға көп уақыт бөлгісі келмейді. Сондықтан ойын басталмас бұрын Аманбол Нарханнан кейбір кедергілерді жылжытуды сұрауы мүмкін. Ол кез келген $i$ ($1 <= i <= n$) кедергісін таңдап, Нарханнан бұл кедергіні бір бірлікке солға немесе бір бірлікке оңға жылжытуды сұрай алады. Бірақ ойынның барлық ережелері (кедергілердің қиылыспауы және бастапқы немесе соңғы нүктенің кедергілердің ішінде жоқ болуы) әрдайым сақталуы керек. Нарханға Аманболдың осы өтінішін орындау үшін $C_i$ секунд қажет болады. Аманбол Нарханнан тіктөртбұрыштарды қалағанша (тіпті $0$ рет) жылжытуды сұрауы мүмкін. Ол ойынды жалпы ең аз қанша уақыт ішінде аяқтай алады? Бірінші жолда екі $n$ және $m$ ($1 <= n <= 5 \cdot 10^5$, $1 <= m <= 3 \cdot 10^6$) бүтін сандары — кедергілер саны және соңғы нүктесінің координатасы берілген. Келесі $n$ жолдардың $i$-ші қатарында төрт бүтін сан $L_i$, $R_i$, $H_i$ және $C_i$ бар: $i$-ші кедергінің сол және оң жақ ұштарының координатасы, биіктігі және қозғалту құны ($1 <= L_i < R_i <= m-1$, $1 <= H_i <= 10^9$, $0 <= C_i <= 3 \cdot 10^6$, бүкіл $i$ үшін $R_i <= L_{i+1}$). Ойынды барынша тез аяқтау үшін Аманболға жалпы неше секунд қажет екенін шығарыңыз. Бұл есеп $6$ ішкі есептен тұрады. Вход

3 10
1 3 5 100
4 6 4 2
7 9 3 100

Ответ

28

Вход

4 15
1 4 3 0
5 6 3 0
6 8 3 0
12 13 3 0

Ответ

21

Бірінші мысалды қарастырайық.

Бірақ Аманбол екінші тіктөртбұрышты $2$ секундта бір бірлікке солға жылжытуды сұраса, ойынды $26$ секундта аяқтай алады. Нәтижесінде $28$ секунд болды.

Есеп C. Макс MEX

Профессор Айдос мектепте информатике пәнінен сабақ береді. Бүгін ол MEX жайлы түсіндірді. Жиынның MEX — осы жиында жоқ ең кіші теріс емес сан. Мысалдар:

• $[0,0,1,0,2]$ жиынының MEXі $3$, себебі $0$, $1$ және $2$ жиында бар, ал $3$ жиында жоқ ең кіші теріс емес сан;
• $[1,2,3,4]$ жиынының MEXі $0$, себебі $0$ жиында жоқ ең кіші теріс емес сан;
• $[0,1,4,3]$ жиынының MEXі $2$, себебі $2$ жиында жоқ ең кіші теріс емес сан;.

Талантты оқушы ретінде Темірлан сабақ кезінде ұйықтауды ұйғарды, ал мұны байқаған Айдос дарынды, бірақ жалқау шәкіртіне мынадай үй тапсырмасымен беруді ұйғарды: Ол Темірланға $n$ карталасы бар колода берді. $i$-ші картаның бетінде $a_i$ және артында $b_i$ саны жазылған. Және ол Темірланға $q$ тапсырыс береді, ал $i$-ші тапсырыс үшін $l_i$, $l_i + 1$, $\dots$, $r_i$ карталарының арасында MEX есептеу керек. Темірлан карталарды өз қалауынша аудара алады және әр тапсырыс үшін ол максималды MEX алғысы келеді. Темірлан ұйықтауын жалғасытырып, сенен осы мәселені шешіп беруіңді өтінді. Бірінші жолда бір бүтін сан $n$ ($1 <= n <= 2 \cdot 10^5$) — колодадағы карталар саны. Екінші жолда $n$ бүтін сан $a_1$, $a_2$, $\dots$, $a_n$ ($0 <= a_i <= n$) — карталардың беткі жағында жазылған сандар. Үшінші жолда $n$ бүтін сан $b_1$, $b_2$, $\dots$, $b_n$ ($0 <= b_i <= n$) — карталардың артқы жағында жазылған сандар. Төртінші жолда жалғыз бүтін сан $q$ ($1 <= q <= 2 \cdot 10^5$) — тапсырыстардың саны. Келесі $q$ жолда екі бүтін саннан $l_i$ және $r_i$ ($1 <= l_i <= r_i <= n$) беріледі. Әр тапсырыс үшін бір бүтін санды шығарыңыз — алуға болатын максималды МЕX. Есеп $7$ бөлімнен тұрады. Вход

3
1 2 2
1 0 3
3
1 2
1 1
1 3

Ответ

2
0
3

Вход

8
2 1 2 4 0 2 0 0
3 1 0 5 2 5 2 2
13
3 7
2 4
4 8
4 8
1 7
1 7
3 6
4 7
4 5
2 6
4 8
3 5
2 8

Ответ

1
2
1
1
6
6
1
1
1
3
1
1
3

Бірінші мысал: Бірінші тапсырыс $l_1 = 1, r_1 = 2$. $1$ және $2$ картаны аударамыз, онда беткі жағында $1$ және $0$ саны көрінеді, олардың MEX $2$ болады. Екінші тапсырыс $l_2 = 1, r_2 = 1$. Картаның екі жағында да $1$ жазылған, ал MEX $[1]$ тең $0$. Үшінші тапсырыс $l_3 = 1, r_3 = 3$. $1$ және $2$ картасын аударамыз, онда беткі жағында $1$,$0$ және $2$ саны көрінеді, олардың MEX $3$ болады.