Реализуйте эффективную структуру данных для хранения элементов и присваивания нескольким подряд идущим элементам одного и того же числа.
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.
Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (g — получить текущее значение элемента по его номеру, a — присвоить всем элементам отрезка новое значение).
Следом за g вводится одно число — номер элемента.
Следом за a вводятся три числа — левый и правый концы отрезка и число value, которое нужно присвоить всем элементам данного отрезка массива (0 ≤ value ≤ 100000).
Выведите в одну строку через пробел ответы на каждый запрос g.
5 2 4 3 1 5 4 g 3 a 2 4 10 g 3 g 1
3 10 2
Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть \(N\) бутылок бесконечной вместимости. В \(i\)-ой бутылке уже содержится \(a_i\) мл воды. Также у них есть бочонок с \(L\) мл воды, из которого можно переливать любой имеющийся объём воды в любую бутылку. Выливать воду из бутылок нельзя. После того как Евгений заканчивает все переливания, он больше не притрагивается к бутылкам, а Родион начинает играть мелодию.
Мелодия состоит из \(M\) нот \(b_1, b_2, \dots, b_M\), которые обязательно надо исполнять в заданном порядке. Ноту \(b_i\) Родион сможет сыграть, если найдется бутылка с \(b_i\) мл воды. Если очередную ноту он исполнить не может, то сильно огорчается и перестает играть. Евгений стремится наполнить бутылки таким образом, чтобы Родион играл как можно дольше. Помогите ребятам узнать, какое максимальное количество начальных нот данной мелодии сможет сыграть Родион при оптимальных действиях Евгения.
В первой строке входного файла содержатся три целых числа \(N\), \(M\), \(L\) - количество бутылок, длина мелодии и объем бочонка соответственно. Во второй строке через пробел расположены \(N\) чисел \(a_i\) (\(i = 1, 2, \dots N\)) - количество мл в \(i\)-ой бутылке. В третьей строке - \(M\) чисел \(b_i\) (\(i = 1, 2, \dots M\)) - последовательность нот в мелодии (каждая музыкальная нота обозначается своим числом, одинаковые ноты - одинаковыми числами). Все числа целые и неотрицательные.
Выведите единственное число - максимальное количество начальных нот мелодии, которые можно сыграть, оптимально заполнив бутылки.
Тесты состоят из четырёх групп.
6 8 179 4 9 23 15 43 7 3 10 14 7 3 8 7 3
0
5 8 5 5 3 8 14 1 10 7 3 7 12 3 3 6
4
2 2 4 6 13 8 10
1
Во время лыжных соревнований \(N\) спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: \(i\)-й лыжник преодолевает 1 км за \(w_i\) минут. Длина трассы равна \(L\) км. Считается, что \(i\)-й лыжник обогнал \(j\)-го (совершил обгон), если он стартовал позже \(j\)-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.
Первая строка входного файла содержит два целых числа \(N\) и \(L\). Во второй строке через пробел расположены \(N\) целых чисел \(w_i\).
Выведите единственное число - суммарное количество обгонов.
Во всех тестах \(1 \le L \le 10^9\), \(1 \le w_i \le 10^9\) при \(i = 1, 2, \dots, N\). Тесты состоят из трёх групп.
2 1 20 19
0
5 3 3 6 2 4 1
7
В одной Очень Известной Летней Школе наиболее популярным видом спорта является волейбол. Для каждого из \(N\) школьников известно его умение играть в волейбол. Перед началом занятий школьников необходимо распределить между двумя тренерами.
Тренеры сочли справедливым следующий алгоритм разделения на две группы. Сначала они выбирают два целых числа \(p\), \(q\) (\(0 < p \le q \le N\)). Затем первый берет себе \(p\) лучших школьников, после чего оба тренера, начиная со второго, берут по очереди по \(q\) лучших школьников из оставшихся, пока их количество не меньше \(q\). В конце очередной тренер просто берет всех оставшихся.
Оба тренера заинтересованы в наиболее справедливом распределении школьников между группами. Поэтому они стремятся найти такие \(p\) и \(q\), чтобы разница суммарных умений между двумя группами школьников оказалась минимальной. При этом, вообще говоря, не обязательно, чтобы количество школьников в каждой из групп было одинаковым.
Помогите тренерам подобрать такие "справедливые" значения \(p\) и \(q\) (\(0 < p \le q \le N\)), при которых разница в суммарных умениях образованных групп школьников по абсолютной величине будет минимальна.
В первой строке входного файла записано единственное целое число \(N\). Во второй строке содержатся \(N\) неотрицательных целых чисел, не превосходящих \(10^9\) - умения школьников играть в волейбол.
Выведите искомые целые значения \(p\) и \(q\) (\(0 < p \le q \le N\)). Если искомых пар несколько, то выведите любую из них.
Тесты состоят из четырёх групп.
8 5 3 3 3 3 3 7 1
1 2
Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа \(N\) и \(K\) (\(1 \leq N \leq 100000\), \(0 \leq K \leq 300000\)), где \(K\) – количество дорог. Каждая из следующих \(K\) строк содержит описание дороги с двусторонним движением – три целых числа \(a_i\), \(b_i\) и \(l_i\) (\(1 \leq a_i,b_i \leq N\), \(1 \leq l_i \leq 10^6\)). Это означает, что имеется дорога длины \(l_i\), которая ведет из города \(a_i\) в город \(b_i\). В последней строке находятся два числа \(А\) и \(В\) – номера городов, между которыми надо посчитать кратчайшее расстояние (\(1 \leq A, B \leq N\))
Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города \(А\) до города \(В\) доехать невозможно, выведите –1.
6 4 1 2 7 2 4 8 4 5 1 4 3 100 3 1
115