Задача 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$). В $i$-й из последующих $n$ строк содержатся четыре целых числа $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$, $R_i <= L_{i+1}$ для всех $i$). Выведите одно единственное целое число — минимальное суммарное количество секунд, необходимое Аманболу для прохождения игры. Данная задача содержит $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$-го отрезка нужно посчитать MEX среди карт $l_i$, $l_i + 1$, $\dots$, $r_i$. Темирлан может переворачивать карты как он хочет и нужно независимо для каждого отрезка найти максимальный МЕХ чисел лицевой стороны. Темирлан решил поспать и попросил вас решить данную задачу за него. В первой строке входных данных задано единственное целое число $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$). Для каждого отрезка выведите одно целое число — максимальный МЕХ который можно получить. Данная задача содержит $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$.