Страница: << 31 32 33 34 35 36 37 Отображать по:
#113539
Продажа картин
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Продажа картин ]
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
32 megabytes

Лука - торговец картинами. У него есть N клиентов, каждому из которых он продает произведения искусства. Каждый клиент может купить либо цветные картины, либо черно-белые, но не те и другие вместе. При этом клиент под номером i готов купить не более a i цветных картин и не более b i черно-белых картин. При этом каждый клиент хочет купить хотя бы одну картину.

У Луки практически неограниченный запас картин, поэтому запросы клиентов не являются для него проблемой. Однако, Лука не любит продавать черно-белые картины, и если окажется, что меньше, чем C людей купили цветные картины, он очень огорчится.

В силу нестабильной экономической ситуации в стране клиенты постоянно изменяют свои запросы, иными словами количество цветных и черно-белых картин, которые они готовы купить. Из-за этого Лука постоянно задается вопросом: "Сколько у меня есть вариантов, как продать клиентам картины, чтобы хотя бы C человек купили цветные картины?". Помогите Луке и защитите его от излишнего беспокойства.

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

Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 105, 1 ≤ C ≤ 20 ). Вторая строка содержит N целых чисел a i ( 1 ≤ a i ≤ 109 ). Третья строка содержит N целых чисел b i ( 1 ≤ b i ≤ 109 ). Четвертая строка содержит одно целое число Q ( 1 ≤ Q ≤ 105 ) - количество изменений требований клиентов. Каждая из следующих Q строк содержит три числа: номер клиента, меняющего требования P ( 1 ≤ P ≤ N ), новое максимальное количество цветных картин, которое он готов купить A p ( 1 ≤ A p ≤ 109 ) и новое максимальное количество черно-белых картин, которое он готов купить B p ( 1 ≤ B p ≤ 109 ).

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

Выведите Q строк, где в q -й строке записано единственное число - количество вариантов продать картины клиентам, чтобы хотя бы C человек купили цветные картины, по модулю 10007 после первых q изменений требований.

Разбалловка для личной олимпиады

Тесты 4-6 — числа n, q не превосходят 1000. Группа тестов оценивается в 30 баллов.

Тесты 7-13 — Полные ограничения. Группа тестов оценивается в 70 баллов.

Примеры
Входные данные
2 2
1 1
1 1
1
1 1 1
Выходные данные
1
Входные данные
2 2
1 2
2 3
2
1 2 2
2 2 2
Выходные данные
4
4
Входные данные
4 2
1 2 3 4
1 2 3 4
1
4 1 1
Выходные данные
66
#113774
Фурье?
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
512 megabytes

Жюри не гарантирует существование решения, выполняющегося на всех тестах с двукратным запасом времени работы.

Для числа 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 групп тестов, баллы за группу выставляются только при прохождении всех тестов группы.

  1. 1 ≤ n ≤ 5 , 5 баллов.
  2. 1 ≤ n ≤ 10 , 5 баллов.
  3. 1 ≤ n ≤ 20 , 10 баллов.
  4. 1 ≤ n ≤ 100 , 10 баллов.
  5. 1 ≤ n ≤ 1000 , 10 баллов.
  6. 1 ≤ n ≤ 5000 , 10 баллов.
  7. 1 ≤ n ≤ 50 000 , 25 баллов.
  8. 1 ≤ n ≤ 100 000 , 25 баллов.

Примеры
Входные данные
3 998244353
Выходные данные
1
9
36
Входные данные
10 3
Выходные данные
1
0
0
0
2
2
0
2
2
0
#113942
Бургеры в McDuck's
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено \(k\) плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более \(k\) бургеров в минуту.

Известно, что в «McDuck's» придут \(n\) клиентов. \(i\)-й из них придёт в момент времени \(t_i\), закажет \(x_i\) бургеров и будет готов заплатить за них \(c_i\) бурлей. Каждый клиент готов ждать заказ в течение \(w\) минут и, если через \(w\) минут после прихода он не получил \(x_i\) бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени \(t_i\). Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.

Менеджеров ресторана заинтересовало, какую максимальную прибыль может получить «McDuck's». Помогите им ответить на этот непростой вопрос. Можно считать, что на готовку бургеров не расходуется никаких денег.

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

В первой строке содержатся три целых числа \(n\), \(k\) и \(w\) (\(1 \le n \le 100\,000\), \(1 \le k \le 10\), \(1 \le w \le 60\)) — число клиентов, число плит и время ожидания клиента, соответственно.

Следующие \(n\) строк содержат описания клиентов, состоящие из трёх целых чисел — \(t_i\), \(x_i\), \(c_i\) (\(1 \le t_i, x_i, c_i \le 10^9\)) — время (в минутах) прихода \(i\)-го клиента, число бургеров, которые он закажет и число бурлей, которые он готов заплатить, соответственно. Клиенты перечислены в порядке возрастания времени прихода, то есть для любого \(i \ge 2\) верно, что \(t_{i - 1} \le t_i\).

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

В единственной строке выведите одно число — максимальную прибыль ресторана.

Примечание

В первом тестовом примере первую котлету можно поставить жариться в момент времени 0 и тогда в момент времени 1 она будет готова и её можно будет дать в бургере первому клиенту. В момент времени 1 можно поставить жариться ещё одну котлету, она будет готова в момент времени 2 и её можно будет дать в бургере второму клиенту.

Примеры
Входные данные
2 1 1
1 1 5
1 1 7
Выходные данные
12
Входные данные
3 2 2
1 6 8
2 5 10
3 4 4
Выходные данные
12
Страница: << 31 32 33 34 35 36 37 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест