Aidos Nurmash

Есеп №1. (Табиғат қорғаушысы)

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

2 seconds

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

512 megabytes

Темірұлан - Каспий аймағының табиғаты мен жануарларын қорғаушылар тобының белсенді мұшесі. Жақында өз туған жеріне серуендеп жүргенде ол ЖранУ есімді сирек кездесетін өсімдікті кездестірді. ЖранУ өте ерекше өсімдік. Олар тек үлкен және ескі ағаштардын көлеңкелерінде ғана өседі. Темірұлан бірінен кейін бірі орналасқан $n$ ағашты тексерді де, әр ағаштың түбіне ЖранУ өсімдігін отырғызуға болатынын немесе болмайтындығын тексерді. ЖранУ өсімдігі Темірұланға ұнағаны сонша, ол әр жыл сайын, $q$ жыл бойы осы өсімдікті отырғызуға бел байлады. Бұл өсімдікті отырғызу кезінде ол $l$ мен $r$ арасында бірінен кейін бірі орналасқан ағаштарды алып, егер ЖранУ өсімдігін отырғызуға болытын болса отырғызады. Өсімдікті отырғызып болған соң, оларды міндетті түрде суғару керек. Ол үшін Темірұлан өзімен бірге өлшемі $k$ болатын суға арналған шелек алды, бұл шелек арқылы қатарынан орналасқан $k$ ағаштардың көлеңкесінде отырғызылған өсімдіктерді суғаруға болады. Темірұлан әр отырғызылған өсімдікті кем дегенде бір рет суғарғысы келеді. Барлық жаңадан отырғызылған өсімдіктерді суғару үшін кем дегенде қанша суға арналған шелек қажет? Назар аударыңыз, Темірұлан әр жыл сайын алдыңғы жылда отырғызылған өсімдіктерді есептемей суғарады.

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

Бірінші жолда екі бүтін сандар беріледі $n$ және $t$ $(1 \le n \le 2\cdot10^5, 0 \le t \le 1)$ — ағаштардың саны және енгізілетін сандарды оқуға арналған тұрақты сан. Келесі $n$ сан $i$-ші ағашты сипаттайды, егер $i$-ші сан 0 болса, онда өсімдікті $i$-ші ағаштың түбіне отырғызуға болмайды, олай болмаса болады. Ағаштар нөлден бастап реттеледі Келесі жолда $q$ $(1 \le q \le 2\cdot10^5)$ саны беріледі — өсімдікті отырғызу саны. Ал келесі $q$ жолдарда үш бүтін саннан беріледі: $a_i$ $b_i$ $c_i$ $(0 \le a_i, b_i, c_i \le 10^9)$ Назар аударыңыз, кесінділердің шеттері $[l_i, r_i]$ және $k_i$ саны кодталған және оларды алу үшін келесі түрлендіруді қолдану керек. { \center $l_i = (a_i \oplus (t*lastans)) \mod n, \quad r_i = (b_i \oplus (t*lastans)) \mod n, \quad k_i = ((c_i \oplus (t*lastans)) \mod n) +1 $ \center
} $lastans$ — соңғы сұраққа жауап (алғашқыда $lastans$ $0$-ге тең). Егер $l_i$ мәні $r_i$ мәнінен үлкен болса, онда $l_i$ мен $r_i$ мәндерінің орынын ауыстыру қажет. Бұл жерде $\oplus$ операциясы биттік XOR немесе жоюшы НЕМЕСЕ. Бұл операция барлық заманауи бағдарламалау тілдерінде бар, С++ және Java тілінде <<$\string^$>>, ал Pascal тілінде <>. $a \mod b$ операциясы $a$-ны $b$-ға бөлгендегі қалдықты алуды білдіреді.

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

$q$ жол шығарыңыз. $i$-ші жолда бір сан шығарыңыз — $i$-ші сұраққа жауап.

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

Бұл есеп бес бөлімнен тұрады, әр бөліменде берілген шектеулер орындалады.

$n \le 100$, $k_i = 1$, $t = 0$. $7$ баллға бағаланады.
$n \le 2000$, $q \le 2000$. $12$ баллға бағаланады.
$n \le 10^5$, $q \le 10^5$, $k_i \le 10$, $t = 0$ . $21$ баллға бағаланады.
$n \le 2\cdot10^5$, $q \le 2\cdot10^5$, $t = 0$ . $23$ баллға бағаланады.
Есепте берілген шектеулер. $37$ баллға бағаланады.

Пример:

Вход

7 0
0 1 1 0 1 1 0
6
0 2 1
0 6 0
0 6 1
1 4 2
0 6 5
1 5 5

Ответ

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

Есеп №2. (ИГО іріктемесі)

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

1 second

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

32 megabytes

Төрт жыл сайын бүкіл елдер арасында <<Информатика бойынша Гладияторлық Олимпиадсы>> өтеді. Бұл сирек кездесетін жарыс, себебі қатысушыларға тек күшпен ғана жеңіп шығуға болмайды, соған қатар қатысушының ақылы жетік болуы керек. Берляндияда қазір бір жағымды қиындық туып отыр, олимпиадаға $N$ әр түрлі үміткерлер бар. Әр үміткердің зияткерлік деңгейін бір санмен бейнеледі, $i$-үміткердің зияткерлік деңгейі $i$-ге тең. Берляндия информатика бойынша күшті ел болғандықтан, олимпиадаға ел атынан кез-келген қатысушылар санын жіберуге болатыны мәлім. Алайда, оған қарамастан ел ішінде іріктеу жасамақшы. Іріктеу раундына бірнеше үміткер алынып, $M$ тур өткізіледі. $i$-турда осы операциялар орындалады:

Егер де осы турда ең болмаса $a_i$ үміткер болса, онда үміткерлердің ішінде ең төмеңгі деңгеймен $a_i$ үміткер кетеді. $i$-тур қайта жүргізіледі.
Егер де осы турда үміткерлер саны $a_i$ кіші болса, онда келесі турға барлық үміткерлер өтеді. $i=M$ болған жағдайда іріктеу аяқталады.

Іріктеуден кейінгі қалатын үміткерлер тізімі жалғыз екенін байқауға болады. Тілшілер барлық бола алатын жағдайларды қарастырып, барлық мүмкін бола алатын бастапқы үміткерлердің тізбегінен іріктеуден өткен үмірткерлердің тізбектерінің санын тапқылары келеді. Осы сан тым үлкен болғандықтан $P$ санына бөлгеннен кейінгі қалдығын шығарыңыз.

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

Бірінші жолда үш бүтін сан $M$, $N$ және $P$ ($1 \le M \le 1000$, $1 \le P, N \le 10^9$) — раундтар саны, үміткерлер саны және қалдық алуға арналған сан берілген. Ескертеміз, $P$ саны міндетті түрде жай сан болып келуі шарт емес. Келесі жолда $M$ бүтін сан $a_i$ ($1 \le a_i \le 1000$) — $i$-шы раундтың саны берілген.

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

Бір сан — есептің жауабын шығарыңыз.

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

Есеп бес бөлімнен тұрады, әр бөлімде есепте берілген шектеулер орындалады:

$n \le 18$. $10$ ұпайға бағаланады.
$n \le 1000$. $18$ ұпайға бағаланады.
$n \le 10^6$, $P = 999999937$. $21$ ұпайға бағаланады.
Есепте берілген шектеулер. $51$ ұпайға бағаланады.

Пример:

Вход

3 4 100000
7 3 4

Ответ

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

Есеп №3. (Әдемі тізбек)

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

1.5 seconds

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

16 megabytes

Тізбекше деп басқа тізбектен кейбір элементтерін өшіріп және басқа элементтердің орнын ауыстырмай алуға болатын тізбекті атаймыз. Сізге көлемі $n$: $a_1, a_2, \ldots, a_n$ және көлемі $m$: $b_1, b_2, \ldots, b_m$ болатын екі тізбек берілген. $k$ бүтін саннан тұратын $c_1, c_2, \ldots, c_k$ тізбегін әдемі деп атаймыз егерде төмендегі шарттар орындалса: \begin{itemize}

k тақ сан.

Барлық $1 < 2 * j < k$ үшін $c_{2*j-1} < c_{2 * j}$ және $c_{2*j+1} < c_{2 * j}$.

$c_1, c_2, \ldots, c_k$ тізбегі $a_1, a_2, \ldots, a_n$ тізбегінің тізбекшесі.

$c_1, c_2, \ldots, c_k$ тізбегі $b_1, b_2, \ldots, b_m$ тізбегінің тізбекшесі.

\end{itemize} Ең үлкен әдемі тізбектің көлемін және ең үлкен әдемі әр түрлі тізбектің санын $10^9 + 9$ санына бөлгендегі қалдығын табу керек.

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

Бірінші жолда бір бүтін сан берілген $n$ ($1 \le n \le 10^4$)~— $a$ тізбегінің көлемі. Екінші жолда $n$ бүтін сан жазылған $a_i$ ($1 \le a_i \le 20000$)~— $a$ тізбегі. Үшінші жолда бір бүтін сан берілген $m$ ($1 \le m \le 10^4$)~— $b$ тізбегінің көлемі. Төртінші жолда $m$ бүтін сан жазылған $b_i$ ($1 \le b_i \le 20000$)~— $b$ тізбегі. Екі тізбектегі сандар бір бос орын арқылы берілген.

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

Екі бүтін сан шығарыңыз - берілген есептің жауабын. Егер шешімі жоқ болса екі нөл шыгарыңыз.

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

Есеп төрт бөлімнен тұрады:

$1 \leq n \leq 20$, $1 \le m \le 10$. Бұл бөлім $9$ ұпайға бағаланады.
$1 \leq n \leq 1000$, $1 \le m \le 20$. Бұл бөлім $9$ ұпайға бағаланады.
$1 \leq n \leq 500$, $1 \le m \le 500$. Бұл бөлім $28$ ұпайға бағаланады.
$1 \leq n \leq 10^4$, $1 \le m \le 10^4$. Бұл бөлім $54$ ұпайға бағаланады.

Пример:

s Вход

Ответ

0 0

Вход

7
1 5 3 4 2 5 2
5
1 3 5 4 2

Ответ

3 6

Вход

Ответ

3 1

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

Есеп №4.

Есеп A. Қызық ойын

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

2 seconds

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

256 megabytes

Жақында Айдос ежелгі тау халықтарының тарихын зерттей отырып, өте қызық ойынға тап болды. Ойынды ойлап табушылар бойынша, бұл ойынның мәдениеттегі орны ерекше, кез келген жастағы адамның дедуктивті ойлау қабілетіне септігін тигізеді екен. Айдос ойынға қызығып, оның замануи баламасын ұсынды. Сізге басында $n$ төбе мен $m$ доғадан тұратын бағдарланбаған граф беріледі. Графтың әр $v$ төбесінің өзіне тиесілі $a_v$ деген мәні бар. Сізге берілген графқа $q$ операция жасау керек. Бұл операциялар төрт түрлі:

Графта бар белгілі екі төбені доғамен байланыстыру
Графта бар белгілі бір доғаны жою
Белгілі бір төбенің мәнін өзгерту
Белгілі бір төбенің көрші төбелерінің арасында мәні $k$-шы болатын төбені табу.

Ескерту. Графта еселенген доғалар кездесуі мүмкін және графтың байланысқан граф екеніне кепілдік берілмейді.

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

Бірінші жолда бос орын арқылы үш бүтін сан $n, m, q$ берілген — төбелердің, доғалардың және операциялардың саны $(1 <= n, m, q <= 2 \cdot 10^5)$. Екінші жолда бос орын арқылы $n$ сан $a_1, a_2, ..., a_n$ берілген — төбелердің мәндері $(1 <= a_i <= 10^9)$. Келесі $m$ жолда графтың доғалары берілген, әр жолда екі сан $u, v$ — $u$ және $v$ төбелерін байланыстыратын бағдарланбаған доға $(1 <= u, v <= n)$. Келесі $q$ жолда операциялардың сипаттамасы берілген. Олардың әрқайсысы келесі сиппатамалардың біреуіне сәйкес келеді:

1 u v — $u$ және $v$ төбелерін бағдарланбаған доғамен байланыстыру.
2 u v — $u$ және $v$ төбелерінің арасындағы доғаны жою. Егер олардың саны бірнеше болса, тек қана біреуі жойылуы керек.
3 u x — $u$ төбесінің мәнін $x$-қа жаңарту.
4 u k — келесі нұсқау бойынша қажет төбені табыңыз: $u$ төбесінің көрші төбелерін бірінші мәндері бойынша, содан соң нөмірі бойынша реттеңіз (екі параметр де өсу ретімен). Пайда болған тізімнен $k$-шы төбені анықтаңыз $(1 <= u, v <= 2 \cdot 10^5, 1 <= x <= 10^9)$.

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

Әрбір 4-ші түрдегі операция үшін жазылған талаптарға сай келетін төбе нөмірін жаңа жолға шығарыңыз.

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

Есеп алты бөлімнен тұрады:

$1 <= n, q <= 100$. 6 ұпайға есептеледі.
$1 <= n, q <= 10000$, осы бөлімде түрі екінші операциялар жоқ. 7 ұпайға есептеледі.
$1 <= n, q <= 50000$. 22 ұпайға есептеледі.
$1 <= n, q <= 200000$, $k=1$, осы бөлімде түрі үшінші операциялар жоқ. 9 ұпайға есептеледі.
$1 <= n, q <= 200000$, осы бөлімде түрі үшінші операциялар жоқ. 12 ұпайға есептеледі.
Есептің толық шектеулері. 43 ұпайға есептеледі.

Пример:

Вход

Ответ

( Aidos Nurmash )
комментарий/решение(1) олимпиада

Есеп №5.

Есеп C. Маглдар шабуылдайды

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

2 seconds

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

256 megabytes

Әлемдік ғаламтор $n$ шыңдармен және $n - 1$ қабырғаларынан құралады. Әр қабырға екі басқа-басқа шыңдарды жалғайды. Осы желіде кез-келген шыңнан басқа шыңдардың барлығына қабырғалар арқылы жетуге болады. Әр шың басында Сиқыршы тұрады. Сиқыршылар — өте жылы шырайлы жаратылыстар, дегенмен, олар тек жұптасып өмір сүре алады. 2 Сиқыршы көршілес шыңдарда тұрғанда ғана жұп құра алады. Әр Сиқыршы тек бір ғана жұп құра алады. Маглдар кейбір шыңдарды бұғаттап, сонымен қатар бұғатталған шыңдардағы Сиқыршыларды да қолға түсіруді шешті. Әр бұғаттау желінің $k$ бұғатталатын шыңдарынан тұрады. Әр бұғатталған шыңнан Маглар сол шыңдағы Сиқыршыны қолға түсіріп, алып кетеді. Бұғаттан кейін байбалам басталап, Сиқыршылар өзіне жұп ізестіреді. Егерде ең болмаса бір Сиқыршы өзіне жұп таба алмаса, Хаос орнайды. Назар аударыңыз, Сиқыршылар жұптар саны көп болатындай, жұптарға бөлінеді. Сиқыршыларда ықтимал бұғаттардың $q$ болжамдары бар. Әр болжам үшін, сол болжам орындалса Хаос орнайтынын анықтаңыз.

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

Бірінші жолда екі сан $n$, $q$ ($1 <= n, q <= 5*10^5$) — шыңдар саны мен болжамдар саны берілген. Келесі $n-1$ жолда екі сан $u$, $v$ ($1 <= u, v <= n$) — арасында қабырғалары бар шыңдар берілген. Келесі $q$ жолда болжамдар берілген. Әр болжам $k, a_1, a_2, \dots, a_k$ $(0 <= k <= n, 1 <= a_i <= n)$ түрінде — бұғатталған шыңдардың саны мен нөмерлері беріледі.

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

Бос жермен бөлінген $q$ сан шығарыңыз. Әр бұғат үшін келген болжамдар ретінде, егер Сиқыршылар бір-біріне жұп таба алса $1$ (Хаос орнамаса), таба алмаса $0$ (Хаос орнаса) шығарыңыз.

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

$sum(k)$ деген барлық болжамдардағы бұғатталған шыңдардың саны. Есеп 5 бөлімнен тұрады: 1. $1 <= n, q, sum(k) <= 3000$, 2 ден көп шыңмен жалғанған шың жоқ. Бөлім $13$ ұпайға бағаланады. 2. $1 <= n, q, sum(k) <= 3000$. Бөлім $17$ ұпайға бағаланады. 3. $1 <= n, q, sum(k) <= 100000$. Бөлім $22$ ұпайға бағаланады. 4. $1 <= n, q, sum(k) <= 100000$. $k_i <= 1$. Бөлім $19$ ұпайға бағаланады. 5. $1 <= n, q, sum(k) <= 500000$. Бөлім $29$ ұпайға бағаланады.

Пример:

Вход

Ответ

1 0 1

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

Есеп №6.

Есеп E. Қиын қосынды

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

2.5 seconds

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

512 megabytes

$n$ элементтен тұратын жиым мен $m$ сұраныстар берілген. Әр сұраныс екі, $l$ және $r$ ($1 <= l <= r <= n$) сандарымен сипатталған. Әрбір сұраныс үшін $l$-ден $r$-ге дейін, барлық ішжиымдардың $f(a[x...y])^T$ қосындын санау керек. Мұндағы $a[x...y]$ бұл бастапқы жиымның $x$-тан $y$-ға дейінгі бөлімі, яғни [$a_{x}, a_{x+1}, ..., a_y$], ($l <= x <= y <= r$) жиымы. Ұзындығы $k$ болатын $b$ жиымы үшін $f(b)$ функциясы, ол $b$ жиымының префикс-максимумымдарын құрайтын, ұзындығы $k$ болатын $c$ жиымын тауып, содан кейін $c$ жиымындағы әртүрлі элементтер санын есептейді. Басқаша айтқанда, $c_i$ = max($b_1, b_2, ..., b_i$) болсын. Сонда $f(b)$ ол $c$ жиымындағы әртүрлі элементтер санына тең. Мысалы, $b = [3, 1, 4, 1, 5, 9, 2, 6, 5]$ үшін префикс-максимумдары $c = [3, 3, 4, 4, 5, 9, 9, 9, 9]$ жиымын құрайды. Кейін $c$ жиымында қанша әртүрлі элементтер бар екенін есептейміз, ол $4$ тең ($3, 4, 5$ және $9$). Сіздің есебіңіз - әр сұраныс үшін, оның барлық ішкі жиымдарының қосындысын табатын бағдарлама жазу. Жауап өте үлкен болуы мүмкін болғандықтан, оны $10^9 + 7$ санына бөлгендегі қалдығын шығарыңыз.

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

Бірінші жолда, үш $n$, $m$ және $T$($1 <= n,m <= 5 \cdot 10^5, 1 <= T <= 2$) бүтін сандары бар. Екінші жолда $n$ бүтін саннан тұратын $a_1, a_2, ..., a_n$($1 <= a_i <= n$) жиыны бар. Келесі $m$ жолда, екі $l_i$ және $r_i$ ($1 <= l_i <= r_i <= n$) сандары бар.

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

$m$ бүтін сан — әр сұранысқа жауапты $10^9 + 7$ модулі бойынша шығарыңыз.

Примеры:

Вход

Ответ

Вход

6 5 1
4 3 2 5 4 6
1 4
2 5
3 6
4 6
1 6

Ответ

Замечание

Бірінші мысалдағы $4$-сұранысты қарастырайық: $l_4 = 1, r_4 = 3$. Сондықтан бізге келесі қосындыларды есептеу керек: $f(a[1...1])^2 + f(a[1...2])^2 + f(a[1...3])^2 + f(a[2...2])^2 + f(a[2...3])^2 + f(a[3...3])^2 = 1 + 2^2 + 2^2 + 1 + 1 + 1 = 12$. $f(a[1..3]) = f([a_1, a_2, a_3]) = f(1, 3, 2) = 2$, өйткені жиымының префикс-максимумымдарын құрайтын жиым бұл $[1, 3, 3]$, және онда екі әртүрлі сан бар. ( Aidos Nurmash )
комментарий/решение олимпиада