Temirlan Baibolov

Есеп №1.

Есеп B. Достар

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

1 second

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

256 megabytes

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

Ответ

Вход

5 4
1 2
1 3
1 4
1 5
4 18 6 16 4

Ответ

Вход

2 0
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$).

( Temirlan Baibolov )
комментарий/решение олимпиада

Есеп №2.

Есеп A. Мұнаралар

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

1.5 seconds

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

256 megabytes

Тізбек бойында кубтардан құралған $n$ мұнара орнатылған. $i$-ші мұнара $a_i$ бірінің үстіне бірі тұрған кубтардан кұралған. Әр мұнараның биіктігі $k$ кубтан көп болмайтындығына кепіл беріледі. Кубтар екі түрлі бола алады — қатып калған және жай. Қатып калған кубқа гравитация әсер етпейді. Жай куб жерге немесе басқа кубтын үстіне түспегенше дейін құлай береді, ал қатып қалған куб сол биіктікте қатып тұрады. BThero сізден кезек-кезек үш түрлі $q$ сұрау береді.

Сізге бір $y$ саны беріледі, $y$ биіктігінде орналасқан барлық кубтар қатып калған кубқа айналады.
Сізге бір $y$ саны беріледі, $y$ биіктігінде орналасқан барлық кубтар жай кубқа айналады.
Сізге бір $y$ саны беріледі, $y$ биіктігінде жаңа лазер орнатылады. Осыған деін осы биіктікте ешқандай лазер орнатылмағанына кепіл беріледі. Лазердің нөмірі ең кіші басқа лазерлармен колданылмаған оң санға тең. Лазерді $y$ биіктігінде орналасқан горизонтал түзу ретінде елестетуге болады және сол лазерге тиген барлық кубтарды жояды. Егер лазер кубты жойса, және сол кубтын орнына гравиция заңы бойынша басқа жай куб құласа, ол кубта жойылады. Бұл процесс кайта қайталануы мүмкін.

Лазерлардын санын $m$ деп белгілейік. Барлық сұраулардан кейін әр лазердің қанша кубты жойғаның шығарыңыз.

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

Бірінші жолда үш бүтін $n$, $q$, $k$ сандары берілген — мұнаралардын саны, сұраулардың саны және мұнарадағы кубтардың санының шектеуі ($1 <= n, q <= 300000$, $1 <= k <= 10^9$). Екінші жолда $n$ бүтін $a_1$, \dots, $a_n$ сандары берілген ($1 <= a_i <= k$). Келесі $q$ жолда $t_i$, $y_i$ форматында сұраулар берілген — $i$-ші сұраудың түрі және сұраудың түріне байланысты сан($1 <= t_i <= 3$, $1 <= y_i <= k$).

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

Пробелдармен бөлінген $m$ бүтін $c_1$, \dots, $c_m$ — әр лазердің жойған кубтардың санын шығарыңыз. $m > 0$ екеніне кіпілдік

Система оценки

Бұл есеп $7$ бөлімге бөлінеді.

Берілгендегі мысал. $0$ баллға бағаланады.
$n, k, q <= 100$. $15$ баллға бағаланады.
$n, k, q <= 5000$, $t_i = 3$ әр $1 <= i <= q$. $8$ баллға бағаланады.
$n, k, q <= 5000$. $13$ баллға бағаланады.
$k <= 300000$. $19$ баллға бағаланады.
$t_i \neq 2$ әр $1 <= i <= q$. $16$ баллға бағаланады.
Есептің бастапқы шектеулері. $29$ баллға бағаланады.

Пример:

Вход

Ответ

10 4 4

( Temirlan Baibolov )
комментарий/решение олимпиада

Есеп №3.

Есеп A. Қосындымен бояу

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

1 second

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

256 megabytes

Сізде $n$ бүтін саннан тұратын $a_1, \ldots, a_n$ массиві бар. Бастапқыда массивтегі әрбір сан ақ түске боялған. Бір операцияда сіз:

Үш $(a_i, a_j, a_k)$ ақ санды таңдайсыз ($1 <= i, j, k <= n$, $i \neq j$, $i \neq k$, $j \neq k$).
Егер $a_i + a_j$ мәні $a_k$ мәнінен үлкен болса, $a_k$ санын қара түске бояйсыз.

Бұл әрекетті мүмкіндігінше қайталауға міндеттісіз. Процесс барысында кейбір сандар қара түске боялады, ал қалғандары ақ болып қалады. Процестің ең соныңдағы мүмкін болатын бояулардың санын санау қажет.

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

Бірінші жолда бір бүтін $n$ саны — массив өлшемі бар ($3 <= n <= 10^5$). Екінші жолда $n$ бүтін сан $a_1, \ldots, a_n$ ($-10^9 <= a_i <= 10^9$) бар.

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

Бір бүтін санды басып шығарыңыз — мүмкін соңғы бояулар саны. Берілген шектеулер бойынша жауап ешқашан $10^{18}$ мәнінен аспайтынын көрсетуге болады.

Примеры:

Вход

3
2 2 5

Ответ

Вход

4
-3 1 2 2

Ответ

( Temirlan Baibolov )
комментарий/решение(2) олимпиада

Есеп №4.

Есеп E. Шоколадтар

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

2.5 seconds

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

256 megabytes

Айбар мен Данияр олимпиада алдында шоколад сатып алуды шешті. Дүкенде $1$-ден $n$-ға дейін нөмірленген шоколадтардың $n$ түрі сатылады делік. Шоколадтың $i$-нші түрінде $a_i$ тәттілік деңгейі бар. Айбар мен Данияр келесі қарапайым схема бойынша шоколад сатып алуға келісті:

Алдымен Айбар ең тәтті шоколадты сатып алады. Сонда Данияр да шоколадтың басқа түрлерінің ішінде ең тәтті шоколадты алады. Ресми түрде айтқанда, Айбар түрі $i$ болатын шоколадты алса, Данияр түрі $j \neq i$ болатын тәттілігі ең жоғары шоколадты сатып алуы керек.
Енді Айбар тәттілігі ең төмен шоколадты сатып алады. Содан кейін Данияр да шоколадтың басқа түрлерінің ішінде тәттілігі ең кішкентай шоколадты сатып алады. Ресми түрде айтқанда, Айбар түрі $i$ болатын шоколадты алса, Данияр түрі $j \neq i$ болатын тәттілігі ең төмен шоколадты сатып алуы керек.

Соңында Айбар мен Данияр сатып алған шоколадтарының тәттіліктерінің қосындысын санайды. Егер олардың есептелген қосындысы бірдей болса, онда достық жеңеді. Мысалы, егер дүкен тәттілік деңгейлері $[1, 4, 6, 3]$ болатын шоколадтың $n = 4$ түрін сатса, Айбар жалпы тәттілігі $6 + 1 = 7$ болатын $3$ және $1$ шоколадтарын сатып алар еді. Ал Данияр жалпы тәттілігі $4 + 3 = 7$ болатын $2$ және $4$ шоколадтарын сатып алып, соңында достық жеңетін еді. Бұл есепте әр түрдің кем дегенде екі шоколады бар деп есептеуге болады. Дүкенде тек $n = 2$ шоколад түрі болса, достардың екеуі де $1$ және $2$ түрінен бір шоколадтан сатып алар еді. Достар ұсақ-түйек болмай, бірден супермаркетке баруды шешті. Супермаркетте тәттілік деңгейлері $b_1, \ldots, b_n$ болатын $n$ шоколад түрлері сатылады. Енді достар қызықты: егер олар шоколадтарды $(i, \ldots, j)$ түрлерінің арасында ғана сатып алатын болса, достық жеңетіндей қанша $1 <= i < j <= n$ жұп бар?

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

Бірінші жолда $n$ — супермаркеттегі шоколад түрлерінің саны ($2 <= n <= 250000$) бар. Екінші жолда $n$ сандар $b_1, \ldots, b_n$ ($1 <= b_i <= 10^9$) бар.

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

Бір бүтін санды басып шығарыңыз — қажетті жұптар саны.

Примеры:

Вход

3
1 2 3

Ответ

Вход

5
1 1 3 2 1

Ответ

Замечание

Екінші мысалда келесі жұптар сәйкес келеді: $(1, 2), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5)$ ( Temirlan Baibolov )
комментарий/решение олимпиада

Есеп №5.

Есеп D. Қосынды-бөлінді кесінділер

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

1 second

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

256 megabytes

Сізге мөлшері $n$ болатын бүтін оң сандардан тұратын $a$ және $b$ массивтері беріледі. Массивтердің екеуі де $1$-ден бастап нөмірленеді. Сізге $1 <= l <= r <= n$ болатын және $a_l + \ldots + a_r$ қалдықсыз $b_l + \ldots + b_r$ санына бөлінетін $(l, r)$ кесінділерінің санын табу керек. Қарапайым сөздермен айтқанда, $a$ массивінің кесіндідегі қосындысы $b$ массивінің тура сол кесіндідегі қосындысына қалдықсыз бөліну керек.

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

Бірінді жолда $n$ саны — массивтердің өлшемі беріледі ($1 <= n <= 10^5$). Екінші жолда $a_1$, \ldots, $a_n$ сандары беріледі ($1 <= a_i <= 10$). Үшінші жолда $b_1$, \ldots, $b_n$ сандары беріледі ($1 <= b_i <= 10$).

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

Бір бүтін сан шығарыңыз — шарттарға сәйкес келетін $(l, r)$ кесінділердің саны.

Система оценки

Бұл есеп $10$ тесттен тұрады. Әр тест $10$ ұпайға бағаланады.

[(1-2)] Есептің берілгеніндегі мысалдар.
[(3-4)] $n = 1$.
[(5-6)] $n = 100$.
[(7-8)] $n = 2000$.
[(9-10)] $n = 100000$.

Примеры:

Вход

3
1 2 3
1 1 1

Ответ

Вход

5
2 3 1 5 4
3 2 2 1 2

Ответ

Замечание

Бірінші мысалда шарттарға $4$ кесінді сәйкес келеді: $(1, 1)$, $(2, 2)$, $(3, 3)$, $(1, 3)$. $(1, 3)$ кесіндісі сәйкес келеді, өйткені $a_1+a_2+a_3=1+2+3=6$ қосындысы қалдықсыз $b_1+b_2+b_3=1+1+1=3$ қосындысына бөлінеді. ( Temirlan Baibolov )
комментарий/решение(1) олимпиада

Есеп №6.

Есеп D. Екі кезек

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

1 second

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

256 megabytes

Екі кезек бар. Біріншісінде $n$ адам тұр, екіншісінде $m$ адам тұр. Бірінші кезек бір адамға $A$ минутта қызмет көрсетеді, екінші кезек бір адамға $B$ минутта қызмет көрсетеді. Санақ $1$-ші минуттан басталады. Әр минут сайын келесілер рет-ретімен болады:

Бірінші кезекте тұрған бірінші адамға қызмет көрсетілсе, ол кезектен шығады.
Екінші кезекте тұрған бірінші адамға қызмет көрсетілсе, ол кезектен шығады.
Бірінші кезекте тұрған соңғы адам, егер ол екінші кезектің соңына ауысқанда оның реттік нөмірі қазіргіден төменірек болса, екінші кезектің соңына ауысады.
Екінші кезекте тұрған соңғы адам, егер ол бірінші кезектің соңына ауысқанда оның реттік нөмірі қазіргіден төменірек болса, бірінші кезектің соңына ауысады.

Барлық адамдарға қызмет көрсетіліп біткендегі уақыт $T$-ны хабарлаңыз.

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

Бірінші және жалғыз жолда төрт бүтін сан $n$, $m$, $A$ және $B$ ($1 <= n, m, A, B <= 10^5$) берілген.

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

Бір бүтін сан — барлық адамдарға қызмет көрсетіліп біткендегі уақыт $T$-ны хабарлаңыз.

Система оценки

Бұл есеп $5$ ішкі есептен тұрады.

Примеры:

Вход

2 3 1 2

Ответ

Вход

5 6 4 4

Ответ

Вход

3 1 2 4

Ответ

Замечание

Бірінші мысалды қарастырайық. Минут $1$. Бірінші кезекте тұрған адамға қызмет көрсетіледі және ол кезектен шығады. Енді $n=1$, $m=3$. Екінші қатардағы соңғы адам бірінші қатардың соңына ауысады. Енді $n=2$, $m=2$. Минут $2$. Бірінші кезекте тұрған адамға қызмет көрсетіледі және ол кезектен шығады. Енді $n=1$, $m=2$. Екінші кезекте тұрған бірінші адамға қызмет көрсетіліп, ол кезектен шығады. Енді $n=1$, $m=1$. Басқа ештеңе болмайды. Минут $3$. Бірінші кезекте тұрған адамға қызмет көрсетіледі және ол кезектен шығады. Енді $n=0$, $m=1$. Басқа ештеңе болмайды. Минут $4$. Екінші кезекте тұрған бірінші адамға қызмет көрсетіліп, ол кезектен шығады. Енді $n=0$, $m=0$. Барлық адамдарға қызмет көрсетілді, сондықтан жауап $T=4$. ( Temirlan Baibolov )
комментарий/решение олимпиада

Есеп №7.

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

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

2 seconds

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

256 megabytes

Жақында Нархан өзінің жеке платформер ойынын құрастырды. Ұқсас жанрдағы көптеген ойындар секілді ойынның барлық әрекеттері екі өлшемді кеңістікте өтеді. Ойын әлемін $(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$ ішкі есептен тұрады.

Примеры:

Вход

Ответ

Вход

Ответ

Замечание

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

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

( Temirlan Baibolov )
комментарий/решение олимпиада