Есеп A. Геологиялық зерттеу

<<КазЖелУгЗол>> компаниясы пайдалы қазбаларды өндіру бойынша ірі ауқымды жоспар дайындауда. Компания $n$ кен орындарын зерттеу үшін геолог Асемді жалдады. Компания тізіміндегі $i$-ші кен орнының күтілетін өндіру көлемін Асем $c_i$-ға бағалады. Кен орындарының жанында қойма салу қажет болғандықтан, өндіру жұмыстары тізімде қатар орналасқан кен орындарында өтеді деп шешілді. Сонымен бірге, компанияның қаржылық талдау бөлімі $f_k(l, r)$-ді $c_l, c_{l + 1}, ..., c_r$ сандары арасындағы мәнінің кемуі бойынша $k$-ші санға тең деп шешті. Егер $l$-дан $r$-ға дейінгі кесіндіде $k$-дан кем сан болса, $f_k(l, r)$ мәні нөлге тең болады. Компания директоры қандай да бір $k$ үшін $S = \sum_{1 <= l <= r <= n}f_k(l, r)$ мәнін білгісі келді (барлық $(l, r)$ кесінділері үшін $f_k(l, r)$ сомасы). Асем $c_i$ мәндерінің дұрыстығына сенімді. $S$ мәнін тиімді есептеу үшін бағдарлама жазуға көмектесіңіз. Бірінші жолда екі сан $n$ және $k$ берілген ($1 <= n <= 10^5, 1 <= k <= min(n, 500)$). Екінші жолда $n$ сандар $c_1, c_2, ..., c_n$ берілген -- кен орындарын бағалау ($1 <= c_i <= 10^7$). Бір бүтін санды -- $S$-ті шығарыңыз. Есеп $9$ бөлімнен тұрады:

1. Есептің шартында берілген тесттер. $0$ ұпайға бағаланады.
2. $n <= 100$. $11$ ұпайға бағаланады.
3. $n <= 5000$, $k = 1$. $11$ ұпайға бағаланады.
4. $n <= 5000$. $12$ ұпайға бағаланады.
5. $n <= 10^5$, $k = 1$. $15$ ұпайға бағаланады.
6. $n <= 10^5$, $k = 2$. $10$ ұпайға бағаланады.
7. $n <= 10^5$, $a_i <= 2$. $9$ ұпайға бағаланады.
8. $n <= 10^5$, $a_i <= 500$. $14$ ұпайға бағаланады.
9. Есептің толық шарттары. $18$ ұпайға бағаланады.

Вход

5 3
1 2 3 2 1

Ответ

10

Вход

7 4
1 1 1 1 1 1 1

Ответ

10

Бірінші мысалда $f_3(1, 3) = f_3(3, 5)= 1, f_3(1, 4) = f_3(1, 5) = f_3(2, 4) = f_3(2, 5) = 2$.

Есеп В. Витя - тасбақа-ниндзя

Витя жаңа тасбақа-ниндзялар тобының мүшесі болғысы келеді. Оған ең басты сынақты өту керек - Донателлоның берген есебін шығару. Донателло Витяға $n$ қатардан және $m$ бағанадан тұратын кесте береді. Кестенің әр торында бір бүтін сан берілген. Басында кестенің сол төменгі бұрышында фишка тұр. Фишканы бір тор төмен немесе оңға жылжытуға болады. Фишка астыңғы оң бұрышта болмағанынша жылжытады. Фишка өткен тордағы сандардың қосындысы жолдың нәтижесі деп аталады(бастапқы және соңғы торлар да саналады). Витяға нәтижесі ең үлкен болатын жол табу керек. Леонардо бұл сынақты Витя үшін өте оңай деп ойлайды . Сол себептен ол есепті қиындатуды шешті. Фишканы жылжытпас бұрын, Витя Леонарданы таблицада бірнеше (мүмкін 0) вертикаль және горизанталь кесуді сұрай алады . Торлардың шетінен ғана кесуге болады және Леонарда кескенде таблица басынан соңына дейін кесіледі. Нәтижесінде, кесте бірнеше бөлімге бөлінеді. Енді фишка кестенің үстінгі сол бұрышындағы бөлімде және оны төменгі немесе оң жақтағы бөлімге ауыстыруға болады, ол астыңғы оң бұрышта болмағанша. Осындай жолдын нәтижесі деп, барлық өткен бөлімдегі торларда жазылған сандардың қосындысын айтамыз. Нәтижені ең үлкен қылатындай кестені кесіп, фишканы жүргізетін жолды табыңыз. Бірінші жолда $n$ және $m$ ($1 <= n <= 1000$, $1 <= m <= 50$). Келесі $n$ жолда $m$ бүтін сан -- $j$-ші сан $i$-ші қатарда $a_{i, j}$ ($-10^{9} <= a_{i, j} <= 10^9$) кестедеші $i$-ші қатарда $j$-ші бағандағы кестедегі жазылған сан. Есептің жауабың шығарыңыз. Есеп $8$ бөлімнен тұрады:

1. Мысалдар. $0$ ұпайға бағаланады.
2. $a_{i, j} > 0$. $5$ ұпайға бағаланады..
3. $a_{i, j} < 0$. $12$ ұпайға бағаланады.
4. $n = 2$. $10$ ұпайға бағаланады.
5. $n, m <= 10$. $10$ ұпайға бағаланады.
6. $n, m <= 40$. $20$ ұпайға бағаланады.
7. $n <= 100$, $m <= 50$. $21$ ұпайға бағаланады.
8. Ешқандай қосымша шектеу жоқ. $22$ ұпайға бағаланады.

Вход

2 2
2000 600
0 4

Ответ

2604

Вход

4 5
4 23 -10 -2 3
0 1 7 -3 0
2 3 -3 30 1
4 -17 8 0 5

Ответ

78

Екінші мысал.

Есеп С. Массивтөбедегі сайлау

Массивтөбе қаласында әкім сайлауы болайын деп жатыр. Массивтөбеде $n$ үй және оларды байланыстыратын $n - 1$ жол бар. Осы жолдар арқылы әр үйден кез келген үйге жетуге болады. Айбар жаңа бастап жүрген блогер. Ол бір жай жолмен жүріп үйдің адамы кімге дауыс беретінің сұрауды видеоға түсіруді шешті. Жай жол деп, әр үйден жәңе әр жолдан ең көп дегенде бір рет өтетін жолды айтамыз. Айбар біледі, видеода көп қарау болмайды, егер ода доминант үміткер болмаса. Үміткер доминант деп аталады, егер ол сұралған адамдардың ішінде жартысынан көп дауыс алатын болса. Сізге $v_1, v_2, ..., v_n$ әр үйдің адамы кімге дауыс берілетіні айтылады. Қызық контент жасау үшін Айбар, доминанты бар қанша әр түрлі жол бар екенің санағысы келеді. $v$ үйінен $u$ға, $u$ үйінен $v$-ға жолдары бірдей болып саналады. Бірінші жолда $n(1 <= n <= 77777)$. Екінші жолда $n$ бүтін сан $v_1,v_2,..,v_n(1 <= v_i <= n)$. Келесі $n - 1$ жолда екі бүтін сан $a$ және $b(1 <= a,b <= n)$ — $a$ және $b$ үйлерінің арасында жол бар екенің айтады. Есептің жауабын шығарыңыз. Есеп $9$ бөліктен тұрады, әр бөлікте келесі шарттар орындалады:

1. Берілген мысалдар. $0$ ұпайға бағаланады.
2. $n <= 100$. $a_i=i$, $b_i=i+1$ барлық $i$ ($1 <= i < n$) үшін. $6$ ұпайға бағаланады.
3. $n <= 2000$. $a_i=i$, $b_i=i+1$ барлық $i$ ($1 <= i < n$) үшін. $7$ ұпайға бағаланады.
4. $n <= 2000$. $8$ ұпайға бағаланады.
5. $a_i=1$, $b_i=i+1$ барлық $i$ ($1 <= i < n$) үшін. $10$ ұпайға бағаланады.
6. $v_i <= 100$. $a_i=i$, $b_i=i+1$ барлық $i$ ($1 <= i < n$) үшін. $9$ ұпайға бағаланады.
7. $a_i=i$, $b_i=i+1$ барлық $i$ ($1 <= i < n$) үшін. $13$ ұпайға бағаланады.
8. $v_i <= 100$. $12$ ұпайға бағаланады.
9. Берілгеніндегі шарттар. $35$ ұпайға бағаланады.

Вход

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

Ответ

13

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

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

1. Сізге бір $y$ саны беріледі, $y$ биіктігінде орналасқан барлық кубтар қатып калған кубқа айналады.
2. Сізге бір $y$ саны беріледі, $y$ биіктігінде орналасқан барлық кубтар жай кубқа айналады.
3. Сізге бір $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$ бөлімге бөлінеді.

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

Вход

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

Ответ

10 4 4

Есеп В. AB

A,B сыныптарынан $N$ оқушы бір қатарда тұр. $i$-ші тұрған оқушы, оның сол жағында $c_i$ оқушы оның сыныбынан емес екенің айтты. Сізге $c$ массивіндегі сандарды араластырып береді. Кез келген оқушылардың орналасу тәртібің табыңыз. Бірінші жолда бір бүтін сан $N(1 <= N <= 1.5\cdot 10^6)$. Екінші жолда $N$ бүтін сан $x_1,x_2,...,x_N(0 <= x_i <= N)$ — $c$ массивын араластырылуы. Оқушылардың бастапқы орналасу тәртібің $a$ жәңе $b$ символынын тұратын, ұзындығы $N$ болатын сөз ретінде шығарыңыз. Егер бірнеше мүмкін дұрыс жауап болса, кез келгенің шығарыңыз. Есеп $9$ бөлімнен тұрады:

1. Берілгеніндегі мысал. $0$ ұпайға бағаланады.
2. $N <= 10^5$. B сыныбынан бірде бір оқушы болмайтындай жауабы бар. $6$ ұпайға бағаланады.
3. $N <= 20$. $10$ ұпайға бағаланады.
4. $N <= 10^5$. B сыныбынан 2 оқушыдан көп болмайтындай жауабы бар. $8$ ұпайға бағаланады.
5. $N <= 10^5$. $c$ массивы $x$ массивына орын араластырмай тең болатын оқушылардың орналасу тәртібі бар. $14$ ұпайға бағаланады.
6. $N <= 40$. $13$ ұпайға бағаланады.
7. $N <= 2000$. $10$ ұпайға бағаланады.
8. $N <= 300000$. $27$ ұпайға бағаланады.
9. $N <= 1500000$. $12$ ұпайға бағаланады.

Вход

4
1 0 2 0

Ответ

bbab

Вход

5
0 0 2 1 3

Ответ

bbaba

Егер $bbab$ бастапқы орналасу тәртібі болса, онда $c_1 = 0, c_2 = 0, c_3 = 2, c_4 = 1$ болады. Араластыру арқылы [1,0,2,0] массивін алуға болады.

Есеп С. Канто марафоны

Жаз келіп, Есмахан таңертең өзінің Канто қаласында жүгіретін уақыты келді деп шешті. Канто қаласы $n - 1$ жолдарымен байланысқан $n$ қиылыстарыдан тұрады. Мұнда кез-келген қиылыстан жолдар бойымен кез-келген басқа қиылысқа жетуге болады. Жоспар бойынша, жүгіру жексенбі күні басталуы керек еді, бірақ сол күні қалада жыл сайын өтетін Канто веломарафоны жоспарланған болатын. Біз $(a,b)$, маршрутын, $a$ бастапқы қиылысы мен $b$ соңғы қиылысы арасындағы жолдар жиынтығымен анықтаймыз, мұнда әрқашан $a < b$. $(a,b)$ маршрутының ұзындығы - ол өтетін жолдардың саны. Есмахан жүгіру кезінде веломарафонның маршрутымен қиылысқаның қаламайды. Сондықтан ол веломарофонмен қиылыспайтын, ең ұзын $(u, v)$ маршрутың білгісі келеді. Сондай-ақ, берілген $k$ санына, Есмахан қанша $ (x,y) $ веломарафонының маршрутың бар екенің білгісі келеді, егер ол тандаған маршруттың ұзындығы $k$ болса. Сізге Канто қаласындағы $n$, қиылыстар саны, берілген. Әрі қарай, екі қиылысты қосатын $ n - 1 $ жол беріледі. Кез-келген қиылыстан жолдар бойымен кез-келген басқа қиылысқа жетуге болады. Осыдан кейін $q$ сұраныстардың саны беріледі. Сұраныстардың екі түрі бар:

1. $x$ $y$, егер сіз веломарафон $(x,y) $ маршрутында өтсе, онда сіз ең ұзақ жолдың ұзындығын табуыңыз керек.
2. $k$, қанша $ (x, y) $ веломарафонының маршрутың бар екенін табуыңыз керек, егер Есмахан тандаған маршруттың ұзындығы $k$ болса.

Бірінші жолда $n$ ($ 2 <= n <= 5 * 10^5 $) Келесі $ n-1 $ жолдарының әрқайсысы жолдардың сиппатталады: $ u $ және $ v $ $ (1 <= v, u <= n, u \ne v) $. Келесі жолда $ q $ ($ 1 <= q <= 5 * 10^5 $) - сұраныстар саны. Келесі $ q $ жолдары сұраныстардың сипаттамаларын қамтиды. $1$ $x$ $y$ $(1 <= x < y <= n) $ - бірінші түрдегі сұраныстар үшін. $2$ $k$ $ (0 <= k <= n - 1 $) - екінші түрдегі сұраныстар үшін Әр сұраныс үшін оның жауабын шығарыңыз Вход

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

Ответ

4
2
2
6
5
12

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

1. Шарттан мысалдар. $ 0 $ баллға бағаланады.
2. $n <= 1000$. $ u_i = i $, $ v_i = i + 1 $ барлық $ i $ ($ 1 <= i < n$). $8$ баллға бағаланады.
3. $ u_i = i $, $ v_i = i + 1 $ барлық $ i $ ($ 1 <= i < n$). 10 баллға бағаланады.
4. $ n, q <= 500 $. 9 баллға бағаланады.
5. $ n, q <= 3000 $. 11 баллға бағаланады.
6. Барлық сұраныстар 1 түр және $x_i = 1$ $ i $ ($ 1 <= i <= q $) үшін кепілдендірілген. 12 баллға бағаланады.
7. Барлық сұраныстар 1 түр екеніне кепілдік беріледі. 12 баллға бағаланады.
8. $ q <= 10 $. $11$ баллға бағаланады.
9. $ u_i = i + 1, v_i = \lfloor \frac {i + 1} {2} \rfloor$ барлық $ i $ $ (1 <= i < n$). $10$ баллға бағаланады.
10. Мәселенің бастапқы шарттары. $17$ баллға бағаланады.