--->
14 задач
<---
Источники
В холле 179 школы, есть информационный стенд размером \(H \times W\) (\(H\) – высота, \(W\) – ширина). На этом стенде размещается информация о кружках, изменениях в расписании, победах в олимпиадах, а также другая важная информация.
Первого сентября стенд был пуст. Одно за другим на нем начали появляться объявления, которые потом не снимались.
Каждое объявление представляет собой полоску бумаги единичной высоты. I-ое объявление представляет собой прямоугольник размером \(1 \times W_i\).
Когда кто-либо вешает объявление на стенд, то он старается повесить объявление как можно выше. Среди возможных верхних мест всегда выбирается самое левое. Если подходящего места для объявления не нашлось, то объявление не вешается на стенд. Ваша задача состоит в том, чтобы для каждого объявления определить, как высоко оно будет располагаться (в каком ряду).
Первая строка содержит три целых числа \(H\), \(W\) и \(N\) (\(1 \leq H, W \leq 10^9\); \(1 \leq N \leq 200 000\)) — размеры стенда и количество объявлений. Каждая из следующих N строк содержит по одному целому числу \(W_i\) (\(1 \leq W_i \leq 10^9\)) — ширину \(i\)-го объявления.
Для каждого из объявлений (в порядке следования во входном файле) выведите номер ряда, в котором оно будет размещено. Ряды занумерованы от \(1\) до \(H\) сверху вниз. Если объявление разместить нельзя — выведите «–1».
3 5 5 2 4 3 3 3
1 2 1 3 -1
Реализуйте структуру данных для эффективного вычисления значения максимального из нескольких подряд идущих элементов массива, а также количества элементов, равных максимальному на данном отрезке.
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление максимума.
В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).
Для каждого запроса выведите в отдельной строке через пробел значение максимального элемента на указанном отрезке массива и количество максимальных элементов на этом отрезке.
5 2 2 2 1 5 2 2 3 2 5
2 2 5 1
Одна очень известная корпорация проводит испытания новой модели собакоподобных роботов. Для этого главный инженер этой компании приобрёл бесконечную прямую в магазине «Всё для новорожденных» и положил по палке в каждой целочисленной точке этой прямой. Кроме того на прямой находится n роботов ( 1 ≤ n ≤ 2·10 5 ). Так как у инженера плохое зрение, он не поставит робота на позицию, больше чем m ( 1 ≤ m ≤ 2·10 5 ). Для каждого робота известна его позиция на прямой x i — (целое число, 1 ≤ x i ≤ m ).
Инженер хочет провести эксперимент по поиску палок роботами. Для этого он по очереди даёт роботам команду находить палку. Порядок выдачи команд инженер определяет сам. После получения команды робот начинает двигаться вправо (по направлению увеличения координаты) до тех пор, пока не найдёт палку (если в точке с роботом уже есть палка, то он останется на месте) и забирает её. Инженер очень жалеет милых собак-роботов, поэтому отдаёт им команды в таком порядке, чтобы суммарное расстояние, пройденное роботами было минимальным .
Роботы-собаки очень нежные и ленивые существа, поэтому готовы приносить палки только в определённое время суток. Условно разобьём сутки на k моментов ( 1 ≤ k ≤ 2·10 5 ), тогда робот с номером i выполнит команду, только если она поступила в момент времени не раньше l i и не позже r i ( 1 ≤ l i ≤ r i ≤ k ). В другие моменты времени собака просто останется на месте и не возьмёт палку даже если она находится прямо перед ней.
Главный инженер компании ещё не выбрал время проведения эксперимента. Для каждого момента времени от 1 до k сообщите какое минимальное суммарное расстояние преодолеют роботы, готовые работать в это время, если инженер выберет порядок отдачи команд оптимально.
В первой строке входного файла заданы 2 целых числа n , m и k — количество роботов, максимально допустимая позиция и моментов времени, соответственно.
В последующих n строках дано описание роботов.
В строке i + 1 заданы 3 целых числа l i , r i и x i — минимальный и максимальный момент времени, в который робот с номером i будет работать и его позиция на прямой.
Выведите k целых чисел — ответ на задачу для каждого момента времени от 1 до k .
n , m , k ≤ 5 — 10 баллов.
n , m , k ≤ 5 000 — 40 баллов.
n , m , k ≤ 2·10 5 — 100 баллов.
2 2 2 1 2 1 1 2 1
1 1
Жюри не гарантирует существование решения, выполняющегося на всех тестах с двукратным запасом времени работы.
Для числа k рассмотрим все такие различные мультимножества положительных чисел, что их сумма в точности k . Например для k = 3 эти множества {1, 1, 1} , {1, 2} , {3} .
Интересностью числа назовем сумму кубов размеров всех различных мультимножеств. Например интересность числа k = 3 равна 3 3 + 2 3 + 1 3 = 27 + 8 + 1 = 36 .
Поскольку задача должна быть интересной, вам нужно посчитать интересность всех чисел от 1 до n по модулю MOD .
В единственной строке входных данных задаются два числа n и MOD ( 1 ≤ n ≤ 10 5 , 1 ≤ MOD ≤ 10 9 + 7 ) — максимальное число, для которого надо посчитать интересность, и модуль.
Модуль не обязательно простой.
Выведите n строк, в i -й строке должна содержаться интересность числа i по модулю MOD .
Данная задача содержит 8 групп тестов, баллы за группу выставляются только при прохождении всех тестов группы.
3 998244353
1 9 36
10 3
1 0 0 0 2 2 0 2 2 0
|
Я на выборы никогда не ходил, но в этот раз точно пойду за Зигги голосовать. Кандидат от народа!
Вдохновившись трудами греческих философов, Спортакус решил избрать главу правительства в Лентяево. Поскольку греческие философы убедили Спортакуса, что демократия является лучшим видом государственного устройства, он решил провести выборы. Для этого он открыл n избирательных участков, пронумерованных от 1 до n . Известно, что на участке с номером i проголосовали a i жителей Лентяево.
После окончания выборов Спортакус решил подвести некоторую статистику явки на выборах. Спортакус знает множество разных статитстических величин, но наиболее показательной он считает k -ю порядковую статистику, поэтому для некоторых регионов и некоторых значений k Спортакус хочет узнать значение k -й порядковой статистики явок на участках данного региона.
Опишем действия Спортакуса более формально. Регионом с границами l и r Спортакус называет множество избиртельных участков, чьи номера лежат на промежутке от l до r включительно. k -й порядковой статистикой массива чисел супергерой называет число, которое бы находилось на k -й позиции в этом массиве, если бы он был упорядочен по возрастанию.
Стефани огорчает, что явка на выборах не соотетствует её ожиданиям, поэтому она решила слегка изменить значения явок на некоторых участках так, чтобы выборы казались более успешными. Для этого она выбирает четыре числа l , r , x и y и на всех избирательных участках региона с границами l и r , на которых явка равна x меняет протокол, после чего явка на этих участках становится равной y .
Напишите программу, отвечающую на запросы Спортакуса с учётом изменений, которые делает Стефани.
В первой строке содержатся два целых числа n и m ( 1 ≤ n , m ≤ 100 000 ) — количество избирательных участков и количество событий.
Во второй строке содержатся n целых чисел ( 1 ≤ a i ≤ n ) — количество людей, проголосовавших на участке с номером i .
В следующих m строках содержатся описания событий. Каждое событие задано в одном из двух форматов.
1 l r x y ( 1 ≤ l ≤ r ≤ n , 1 ≤ x , y ≤ n ) обозначает, что Стефани на всех участках региона с границами l и r и явкой x установила явку равной y .
2 l r k ( 1 ≤ l ≤ r ≤ n , 1 ≤ k ≤ r - l + 1 ) обозначает, что Спортакуса интересует значение k -й порядковой статистики явок на участках в регионе с границами l и r .
Для каждого вопроса Спортакуса выведите ответ на него.
Группа 1 (10 баллов) 1 ≤ n , m ≤ 100 . Для прохождения этой подгруппы требуется прохождение тестов из условия.
Группа 2 (10 баллов) 1 ≤ n ≤ 5000, 1 ≤ m ≤ 100 000 , нет запросов первого типа. Для прохождения этой подгруппы требуется прохождение тестов из условия.
Группа 3 (10 баллов) 1 ≤ n , m ≤ 100 000 , нет запросов первого типа. Для прохождения этой подгруппы требуется прохождение группы 2.
Группа 4 (20 баллов) 1 ≤ n , m ≤ 100 000 , в запросах первого типа l = r . Для прохождения этой подгруппы требуется прохождение группы 3.
Группа 5 (50 баллов) Без дополнительных ограничений. Для прохождения этой подгруппы требуется прохождение всех предыдущих групп.
3 3 2 3 3 2 1 3 1 1 1 3 3 1 2 1 3 2
2 1