ВШЭ_дивизион_2

Задача A. Bumblebee (Ограничение по времени: 2 секундыб Ограничение по памяти: 256 мегабайт)

В штабе автоботов Bumblebee обнаружил n энергоядер, у каждого из которых есть уровень
мощности a_i
.
Bumblebee заметил интересную особенность этих ядер: они могут объединяться только с ядрами
той же четности.
За одну операцию Bumblebee может выбрать два энергоядра одной четности, объединить их
— после этого оба ядра исчезают, а вместо них появляется новое энергоядро с мощностью, равной
сумме их мощностей.
Полученное ядро можно использовать в следующих объединениях.

Помогите Bumblebee определить, какую максимальную мощность одного энергоядра можно по-
лучить после выполнения нескольких операций, возможно, ни одной.

Формат входных данных
В первой строке содержится одно целое число n (1 ⩽ n ⩽ 10⁵).
Во второй строке содержатся n целых чисел a₁, a₂, . . . , a_n (1 ⩽ a_i ⩽ 10⁹).

Формат выходных данных

Выведите одно целое число — максимальную мощность одного энергоядра, которое можно получить.

Примеры

входные данные	ожидаемый ответ
3 1 2 7	10
4 2 4 8 67	67
2 99 100	100

Замечание
В первом примере можно объединить ядра 1 и 7, получив 8, а затем объединить 8 и 2, получив 10.
Во втором примере чётные ядра можно объединить в ядро мощности 14, но ядро 67 останется отдельно. Ответ равен 67.
В третьем примере ядра имеют разную чётность, поэтому объединить их нельзя. Ответ равен 100.

Задача B. Прыжки через козла (Ограничение по времени: 1 секунда,Ограничение по памяти: 256 мегабайт)

На уроке физкультуры мальчики и девочки прыгают через гимнастического козла.
В классе n мальчиков и m девочек.
Про каждого мальчика известна максимальная высота, которую он способен перепрыгнуть:
a₁, a₂, . . . , a_n.
Про каждую девочку известна максимальная высота, которую она способна перепрыгнуть:
b₁, b₂, . . . , b_m.
Учитель выбирает две целые высоты:
высоту x для мальчиков и высоту y для девочек.
Мальчик с номером i перепрыгнет козла, если ai ⩾ x.
Девочка с номером i перепрыгнет козла, если bi ⩾ y.

Учитель хочет, чтобы количество перепрыгнувших мальчиков совпало с количеством перепрыгнувших девочек.
Среди всех способов выбрать высоты x и y найдите наибольшее возможное значение этого (одинакового для мальчиков и девочек) количества.
Формат входных данных
В первой строке содержатся два целых числа n и m (1 ⩽ n, m ⩽ 10⁵) — количество мальчиков и девочек.
Во второй строке содержатся n целых чисел a₁, a₂, . . . , a_n (1 ⩽ a_i ⩽ 10⁹) — максимальные высоты для мальчиков.
В третьей строке содержатся m целых чисел b₁, b₂, . . . , b_m (1 ⩽ b_i ⩽ 10⁹) — максимальные высоты для девочек.
Формат выходных данных
Выведите одно целое число — максимальное возможное одинаковое количество мальчиков и девочек,
которые смогут перепрыгнуть выбранные для них высоты.
Примеры

стандартный ввод стандартный вывод

Входные данные	Выходные данные
5 4 5 4 3 2 1 5 4 3 3	4
3 4 5 5 1 9 3 3 3	0
5 3 10 9 8 5 1 4 3 2	3
1 1 11 1000000000	1

Замечание
Пример 1. Выберем x = 2 и y = 3. Высоту x = 2 перепрыгнут мальчики со значениями 5, 4, 3, 2
— их 4. Высоту y = 3 перепрыгнут все 4 девочки (значения 5, 4, 3, 3). Получаем 4 = 4. Большего
добиться нельзя: девочек всего 4.
Обратите внимание, что ровно 3 справившихся девочек получить невозможно: при y = 3 их 4, а
при y = 4 — уже только 2, потому что две девочки имеют одинаковое значение 3.
Пример 2. Для мальчиков (значения 5, 5, 1) количество справившихся может быть равно лишь
0, 2 или 3: высоту 5 сразу берут двое. Для девочек (значения 9, 3, 3, 3) — лишь 0, 1 или 4: трое имеют
значение 3. Единственное общее значение — 0. Достаточно назначить высоты больше всех значений,
и тогда не справится никто.
Пример 3. Выберем x = 8 и y = 2. Высоту x = 8 перепрыгнут мальчики 10, 9, 8 — их 3. Высоту
y = 2 перепрыгнут девочки 4, 3, 2 — их тоже 3. Хотя мальчиков может справиться и больше (вплоть
до 5), девочек всего 3, поэтому максимум одинакового количества равен 3.
Пример 4. Высоты для мальчиков и девочек выбираются независимо. Выберем x = 1 и y = 10⁹ :
единственный мальчик и единственная девочка перепрыгнут свои высоты, ответ равен 1.

Задача C. Стоимость сортировки перестановки (Ограничение по времени: 1 секунда, Ограничение по памяти: 256 мегабайт)

Дана перестановка p₁, p₂, . . . , p_n чисел от 1 до n.
За одну операцию можно выбрать подотрезок p_l, p_l+1, . . . , p_r длины k = r − l + 1,
если эти числа образуют перестановку чисел от 1 до k
(то есть каждое число от 1 до k встречается в этом отрезке ровно один раз).

После этого разрешается произвольным образом переставить элементы внутри выбранного по-
дотрезка. Стоимость такой операции равна k.

Требуется найти минимальную суммарную стоимость, необходимую для того, чтобы сделать
перестановку упорядоченной, то есть получить массив 1, 2, . . . , n.
Формат входных данных
В первой строке содержится одно целое число n (1 ⩽ n ⩽ 10⁵).
Во второй строке содержатся n целых чисел p₁, p₂, . . . , p_n (1 ⩽ p_i ⩽ n).
Гарантируется, что массив p является перестановкой чисел от 1 до n.
Формат выходных данных
Выведите одно целое число — минимальную суммарную стоимость, необходимую для сортировки
перестановки.
Примеры

входные данные	ожидаемый результат
2 2 1	2
3 2 1 3	2
6 2 1 5 4 3 6	5

Замечание
В первом примере достаточно выбрать числа p₁, p₂. Они образуют перестановку чисел от 1 до 2,
поэтому их можно поменять местами. Стоимость такой операции равна 2.
Во втором примере снова достаточно выбрать числа p₁, p₂ и отсортировать их. Третий элемент
уже стоит на своем месте, поэтому ответ по-прежнему равен 2.
В третьем примере один из оптимальных способов сначала выбрать числа p₁, p₂ и упорядочить
их. Затем провести операцию с числами p₃, p₄, p₅. Стоимость первой операции равна 2, второй - 3,
поэтому ответ равен 5.
Для сравнения, ту же перестановку можно привести к отсортированному виду и другими двумя
операциями: сначала упорядочить числа p₁, p₂, а затем числа p₁, p₂, p₃, p₄, p₅. Но суммарная стои-
мость в этом случае будет равна 7, что не оптимально.

Задача D. Арбузы и Олег ( Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт)

Капибара Олег работает в зоопарке. Каждый день он пересчитывает запасы арбузов для всех животных.
В зоопарке есть 10⁹ клеток, пронумерованных от 1 до 10⁹. Изначально в каждой клетке не лежит ни одного арбуза.
Олегу дали m поручений. Каждое поручение означает, что Олегу необходимо положить по w_i арбузов в каждую клетку от l_i до r_i включительно.
Олег выполнил все поручения и решил выписать в массив a для каждого арбуза номер клетки, в которой он находится.
Олег очень любит статистику, поэтому он придумал некоторую операцию над массивом a.
Для каждого целого числа x обозначим c_x количество элементов массива a, равных x.
Тогда новый массив a состоит из всех положительных значений c_x.
Олег решил применить такую операцию к массиву ровно t раз и после этого посчитать, сколько различных элементов окажется в конечном массиве.

Так как у Олега очень много капибарных дел, он очень просит вас помочь ему с решением этой несложной задачи.
Формат входных данных
В первой строке содержатся два целых числа m (1 ⩽ m ⩽ 10⁵) — количество поручений и t (0 ⩽ t ⩽ 10⁹) — количество операций,
которые необходимо применить к массиву.
В следующих m строках содержатся по три целых числа l_i, ri и w_i (1 ⩽ li ⩽ ri ⩽ 10⁹, 1 ⩽ wi ⩽ 10⁵), описывающих каждое поручение Олегу.
Формат выходных данных
Выведите одно целое число — количество различных чисел в массиве после применения операции ровно t раз.
Примеры

входные данные	ожидаемый результат
2 0 1 3 1 5 6 2	5
3 1 1 4 2 3 6 1 5 5 3	4
4 2 1 2 5 3 5 7 6 9 11	4

Замечание
В первом примере массив a будет выглядеть следующим образом: [1, 2, 3, 5, 5, 6, 6].
Различные элементы массива a: [1, 2, 3, 5, 6].
В этом примере не нужно делать ни одной операции, значит, ответ равен 5.
Во втором примере изначально массив a выглядит так: [1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6].
После первой операции массив будет выглядеть следующим образом: [2, 2, 3, 3, 4, 1].
Различные элементы этого массива: [1, 2, 3, 4].
Значит, ответ равен 4.