Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Игра PitCraft происходит в двумерном мире, который состоит из блоков размером 1 на 1 метр.

Остров игрока представляет собой набор столбцов различной высоты, состоящих из блоков камня и окруженный морем.

Над островом прошёл сильный дождь, который заполнил водой все низины, а не поместившаяся в них вода стекла в море, не увеличив его уровень. По ландшафту острова определите, сколько блоков воды осталось после дождя в низинах на острове.

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

В первой строке записано натуральное число N (0 <= N <= 100 000) количество столбцов, задающих ландшафт острова.

Во второй строке записано N натуральных чисел H_i (1 <= Hi <= 10⁹) высоты столбцов.

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

Выведите одно число количество блоков занятых водой.

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

Решения, верно работающие при N <= 100, будут набирать не менее половины баллов.

Ввод	Вывод
11 2 5 2 3 6 9 3 1 3 4 6	18

Замечание

Пример соответствует рисунку. Черным цветом обозначен камень, серым вода.

Линейные структуры Префиксные суммы(минимумы, ...)

✓ 52✗ 209700средняяВойти и решать

Путь в никуда#24761

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

Утром Колобок решил проанализировать свой сон. Он догадался, что в каждой клетке он был максимум один раз, но никак не может вспомнить, сколько клеток он посетил. Колобок просит вас написать программу, которая посчитает количество посещённых им клеток.

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

Бинарный поиск Деревья Префиксные суммы(минимумы, ...)Разреженные таблицы (sparse table)Структуры данных

✓ 17✗ 49800средняяВойти и решать

Украшение ёлки – 2#24638

И вот вновь наступил Новый Год, и Васе снова понадобилось наряжать ёлку. Но, памятуя о своих прошлогодних неудачах (Вы о них знаете, если решали прошлогодний контест), он купил в магазине брендовые ударопрочные шарики. К сожалению, на ёлку в результате денег почти не осталось, и её пришлось покупать у какого-то индуса. Поэтому ёлка имеет форму полного двоичного дерева глубины N – на верхушке только одна ветка, и под каждой веткой, кроме самых нижних, снизу растёт ровно две. В самом низу, соответственно, под ветками только Васин немытый пол.

Но когда Вася приступил к украшению, он понял, что совершил страшную ошибку. Ударопрочные шарики были одноцветными и скучными, поэтому Вася не мог развесить их как попало, как он делал это раньше. Пришлось ему разрабатывать алгоритм украшения. Для начала он соотнёс каждому цвету его индекскрасоты – параметр от 0 до 10⁹. Чем он больше, тем более красивым кажется Васе шар этого цвета. Потом он случайным образом развесил шарики у пола (на каждую ветку Вася всегда вешает только один шар). Для всех остальных веток Вася смотрел на их нижних соседей, определял, какой из висящих на этих ветках шариков красивее, и вешал на эту ветку точно такой же.

Когда это муторное дело было наконец завершено, он посмотрел на ёлку и понял, что неудачно выбрал нижние шарики. Но Вася от этой мороки с шариками уже почти пропустил свой любимый новогодний сериал, поэтому попросил Вас помочь ему закончить украшение побыстрее.

Нижние ветви пронумерованы от 1 до 2^(N- 1), более верхним Вася из лени решил номера не давать. Вася подаёт на вход два вида запросов. В первом он заменяет какой-либо шар в нижнем уровне с номером k на шар цвета c, и хочет узнать, на скольких слоях веток (кроме нижнего) ему придётся перевесить шары, чтобы ёлка по-прежнему подходила под описанный выше алгоритм. Во втором он хочет узнать цвет самого красивого шара в секторе от l до r. К сектору относятся все ветки нижнего слоя с номерами от l до r включительно, а также все находящиеся над ними ветки.То есть, если N = 3, то к секторуот 1 до 2 относятся ветки 1 и 2, а также третья ветка, находящаяся между ними чуть выше.

Формат ввода

В первой строке задана глубина ёлки N (N<= 15) и количество запросов M (M<= 10⁷). Во второй строке задана первоначальная развеска нижних шариков, представленная их индексами красоты. В следующих M строках заданы запросыдвух типов (первый обозначен цифрой 1, а второй, как ни странно, 3). Описание запросов дано выше.

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

Нужно вывести Mстрок, содержащих ответы на запросы.

Пример

Ввод:

4 5

1 1 2 3 100 7 11 3

3 1 8

3 2 4

1 5 4

3 1 8

1 5 9

Вывод:

100

Дерево отрезков, RSQ, RMQ Префиксные суммы(минимумы, ...)

✓ 1✗ 11 200средняяВойти и решать

Assault#23586

В то время, пока обороняющиеся отвлеклись на Блейза, Корвин начал штурм города. Для того, чтобы его армия вошла в город, ему нужно пробить брешь в стене. В его распоряжении есть целый флот, из которого он собирается обстреливать стены города. Стена являются линией из n сегментов, пронумерованных от 1 до n.

Корвин хорошо помнит, насколько укреплен каждый сегмент стены. К сожалению, с тех пор как Корвин последний раз был в Амбере, сегменты несколько раз перестраивали, поэтому их укрепленность могла измениться, поэтому Корвин владеет устаревшей информацией.

Но Джерард не только согласился отвести свой флот из бухты Амбера, благодаря чему флоту Корвина удалось добраться до Амбера с целым и невредимым флотом, но и предоставил ему журнал с m записями, в котором в i-ой записи указано, что были перестроены сегменты с l_i по r_i, а также сказано, насколько изменилась укрепленность всех сегментов (укрепленность каждого сегмента на отрезке [li; ri] изменяется на одно и тоже значение t_i).

Корвин m раз предлагает выстрелить по сегментам стены с l по r из p кораблей. Известно, что брешь будет пробита, если на отрезке [l; r] есть хотя бы один сегмент с укрепленностью меньше p. Вы должны ответить ему, будет ли пробита брешь (вывести "YES"), или нет (вывести "NO").

Входные данные

На первой строке находятся числа n, m и k (1 <= n, k <= 100000, 1 <= m <= 10000) - количество сегментов, записей и запросов от Корвина соответственно.

На второй строке находятся числа a₁,..., a_n (0 <= a_i <= 10).

В следующих m строках содержатся числа l, r, t (1 <= l <= r <= n, -10 <= t <= 10).

В следующих k строках содержатся числа l, r, p (1 <= l <= r <= n, 1 <= p <= 1000).

Выходные данные
В i-ой строке выведите ответ на i-ый запрос Корвина.

Примеры

№	Входные данные	Выходные данные
1	10 3 3 123 398 287 190 76 15 407 312 323 659 4 9 -99 10 10 -82 4 10 76 9 10 32 5 6 283 4 4 983	NO YES YES

Дерево отрезков, RSQ, RMQ Префиксные суммы(минимумы, ...)

✓ 33✗ 111700средняяВойти и решать

Кладовка из Простоквашино#21996

Сразу же после заселения в новый дом в Простоквашино кот Матроскин, Шарик и дядя Фёдор затеяли ремонт. Непосредственно перед его началом они обнаружили, что в доме отсутствует кла- довка для стройматериалов, и наспех пристроили её к дому. Как только вспомогательное строение было готово, встал вопрос о необходимости провести туда электричество и повесить лампочку.

Обсудив вопросы электрификации новых помещений с почтальоном Печкиным, наши герои узна- ли много полезной информации. Чтобы посетители не мучились с выбором, в деревенском магазине продаётся только один вид лампочек, зато в неограниченных количествах. Стоит одна лампочка ни дорого, ни дёшево, а ровно C рублей. Правда, лампочки в магазине не самые качественные, и вклю- чить каждую из них можно только K раз, а на K + 1 включение она перегорает. Недостаток этот компенсируется тем, что во включенном состоянии лампочка перегореть не может. К сожалению, электроэнергия в Простоквашино недешевая, и каждая минута работы лампочки обойдется дяде Фёдору и его друзьям в D рублей.

Узнав всё это, экономный Матроскин составил поминутный график из N предполагаемых посе- щений кладовки. Каждый визит в новое помещение задаётся моментом входа ai и моментом выхода bi . Таким образом, i-й визит продолжается ровно b_i − a_iминут.

Разумеется, во время посещения свет в кладовке должен быть включён. Если в начале очередного визита лампочка не горит, то посетитель сразу её включает, а вот уходя он может как выключить свет, так и оставить его включенным. Если во время очередного включения лампочка перегорает, то её приходится немедленно заменить. Теперь Матроскина интересует минимальное количество рублей, которое придётся потратить, чтобы выполнить все запланированные визиты в кладовку. Изначально в помещении уже висит новая лампочка в выключенном состоянии.

Формат входных данных
В первой строке входных данных записаны четыре целых числа N, K, C, D — количество пла- нируемых посещений кладовки, количество успешных включений для одной лампочки, стоимость покупки лампочки и стоимость минуты работы лампочки соответственно (1 <= N, K <= 200 000, 1 <= C, D <= 10⁹ ). В следующих N строках даны по два целых положительных числа ai и bi , описывающих пред- полагаемые визиты в кладовку (1 <= a_i < b_i <= 10⁹ ). Посещения не пересекаются по времени и упорядочены, то есть b_i < a_i+1.

Формат выходных данных
Выведите одно целое число — минимальное количество рублей, которое придётся потратить жителям дома, чтобы выполнить все запланированные визиты в кладовку при свете.

Ввод	Вывод
1 2 5 6 3 5	12
3 1 15 10 1 3 4 5 30 35	105

Замечание
Замечание В первом примере достаточно заплатить только за электроэнергию: лампочка должна быть включена на третьей минуте и выключена на пятой, стало быть, суммарные затраты составляют (5 − 3) × 6 = 12.
Во втором примере выгодно не выключать лампочку между первым и вторым посетителем, а для третьего использовать уже новую лампочку

Динамическое программирование Динамическое программирование: один параметр Префиксные суммы(минимумы, ...)

✓ 13✗ 1651 000средняяВойти и решать

Призы#21887

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.
Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.
Алиса хорошо знает Боба, и для каждого приза выяснила его ценность для Боба, которая является целым положительным числом. Алиса обижена на Боба и хочет выбрать свои призы так, чтобы суммарная ценность призов, которые достанутся Бобу, была как можно меньше. При этом Алису не волнует, какие призы достанутся ей.

Требуется написать программу, которая по информации о ценности призов и значению k определит, для какого минимального значения x Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — общее количество призов и k — количество подряд идущих номеров призов, которое должен выбрать каждый из победителей (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3). Вторая строка содержит n целых положительных чисел: a1, a2, …, an. Для каждого приза указана его ценность для Боба (1 ≤ ai ≤ 10⁹ ).

Формат выходного файла
Выходной файл должен содержать одно число — минимальное значение x, для которого Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Пример
Ввод:
10 2
1 2 4 5 2 4 2 2 1 6
Вывод:
7

Пояснение к примеру
В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.

Префиксные суммы(минимумы, ...)

✓ 15✗ 1821 100средняяВойти и решать

Universe#21788

Наша вселенная представляет собой n-мерный прямоугольный параллелепипед. Множество измерений вселенной B = {a[i] : 1<=i<=n}.

Множество B такого, что его первые b элементов являются измерениями b-мерного подпараллелепипеда.

Перед учеными встал ряд вопросов типа: какое пространство находится внутри k-мерного подпараллелепипеда, если предположить, что пространство внутри m-мерного нулевое.

Напишите программу, которая даст ответ на вопросы ученых.

Входные данные:

Все числа неотрицательные.

В первой строке вводятся целые числа (n, q <= 10^5) размерность нашей вселенной и количество вопросов, интересующих ученых соответственно.

Во второй строчке вводятся n целых чисел - измерения вселенной, каждое из которых не превосходит (10^18 - 14)

Далее следует q строк по два числа, однозначно задающие вопрос указанного типа, интересующий ученых - m, k. (m, k <= n)

Выходные данные:

Программа должна выводить q строк по одному числу. На i-ой строке должен распологаться ответ на i вопрос указанного типа.

Пример:

INPUT:

3 1

1 2 3

0 3

OUTPUT:

Пояснение:

Т.к. пространство внутри 0 мерного подпараллелепипеда (точки) нулевое (по условию), то пространство внутри 3-х мерного (пространство внутри 3-х мерного - объем) считается по обычной формуле: 1*2*3 = 6

Автор: Иван Шершнев

Префиксные суммы(минимумы, ...)

✓ 5✗ 35900средняяВойти и решать