#3328

Максимум на подотрезках с добавлением на отрезке

Темы: [Дерево отрезков, RSQ, RMQ]

Реализуйте эффективную структуру данных для хранения массива и выполнения следующих операций: увеличение всех элементов данного отрезка на одно и то же число; поиск максимума на отрезке.

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

В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.

Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (m — найти максимум, a — увеличить все элементы на отрезке).

Следом за m вводятся два числа — левая и правая граница отрезка.

Следом за a вводятся три числа — левый и правый концы отрезка и число add, на которое нужно увеличить все элементы данного отрезка массива (0 ≤ add ≤ 100000).

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

Выведите в одну строку через пробел ответы на каждый запрос m.

Примеры

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

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

4 104 104

#3329

Дерево интервалов с присваиванием на отрезке

Темы: [Дерево отрезков, RSQ, RMQ]

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

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

В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.

Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (g — получить текущее значение элемента по его номеру, a — присвоить всем элементам отрезка новое значение).

Следом за g вводится одно число — номер элемента.

Следом за a вводятся три числа — левый и правый концы отрезка и число value, которое нужно присвоить всем элементам данного отрезка массива (0 ≤ value ≤ 100000).

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

Выведите в одну строку через пробел ответы на каждый запрос g.

Примеры

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

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

3 10 2

#3330

Футболки

Темы: [Жадный алгоритм]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2010-2011, Заключительный этап, Тур 1, Задача A ]

Array

Петя часто ездит на олимпиады, и потому у него накопилось много футболок. Все футболки он делит на три типа: белые, чёрные и цветные. Каждое утро он выбирает футболку и носит её весь день. Петя любит ходить только в свежих футболках, и поэтому, если он уже надевал одну, то следующий раз он наденет её только после стирки. Его мама не стирает вместе футболки разных типов (иначе они полиняют). Кроме того, мама соблюдает инструкции по оптимальной загрузке стиральной машинки, и для стирки ей требуется ровно \(K\) футболок. При этом, конечно, стирать уже чистые футболки она не будет. Подразумевается, что мама стирает футболки сразу же, как ее об этом попросит Петя, и на следующий день он уже может их надевать.

Один из типов футболок Петя любит больше остальных, отчасти из-за того, что количество футболок этого типа позволяет носить только их. Но однажды Пете сказали, что он одевается не “по моде”, на что Петя обиделся и поспорил, что он сможет \(N\) дней одеваться модно. По моде, принятой в их школе, нельзя ходить два дня подряд в однотипной футболке и нельзя прийти в футболке того же типа ровно через неделю, после того как ты ее надел (например, два понедельника подряд). Школьная мода распространяется и на те дни, когда в школу ходить не надо.

Петя хочет знать, может ли он выиграть спор и, если может, то в каком порядке ему нужно надевать футболки в течении этих \(N\) дней. Он просит вас ему помочь.

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

Во входном файле содержатся пять целых чисел \(N, W, B. C\) и \(K\), разделенных пробелами — число дней, которые Петя должен носить футболки “по моде”, количество белых, черных и цветных футболок, имеющихся у него соответственно, и количество грязных однотипных футболок, которое согласится стирать мама. Гарантируется, что хотя бы одно из чисел \(W, B, C\) не меньше \(K\). \(1 \le N \le 1000, 1 \le K \le 1000, 0 \le W \le 1000, 0 \le B \le 1000, 0 \le C \le 1000\).

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

В первой строке выходного файла выведите единственное слово YES или N0 — ответ на вопрос задачи. Если ответ YES, то во второй строке выведите \(N\) символов, где \(i\)-ый символ означает цвет футболки, которую Петя будет носить в \(i\)-ый день. Символ “W” означает белый цвет, “В” — черный, “С” — цветной.

Примечание

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

Тесты 1-3, из условия, оцениваются в 0 баллов.

1. В тестах этой группы среди чисел \(W, B\) и \(C\) хотя бы одно равно нулю. Эта группа оценивается в 50 баллов, при этом баллы начисляются только при прохождении всех тестов группы (при этом прохождения всех тестов из условия не требуется).

2. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1 группы. Некоторые тесты этой группы объединяются в подгруппы, баллы за каждую подгруппу ставятся только при прохождении всех тестов подгруппы

Примеры

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

2 5 0 4 1

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

YES
WC

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

4 3 4 5 3

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

YES
CWCW

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

10 3 2 1 3

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

NO

#3331

Мелодия

Темы: [Жадный алгоритм] [Бинарный поиск] [Дерево отрезков, RSQ, RMQ] [Двоичное дерево поиска]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2010-2011, Заключительный этап, Тур 1, Задача B ]

Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть \(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\)) - последовательность нот в мелодии (каждая музыкальная нота обозначается своим числом, одинаковые ноты - одинаковыми числами). Все числа целые и неотрицательные.

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

Выведите единственное число - максимальное количество начальных нот мелодии, которые можно сыграть, оптимально заполнив бутылки.

Примечания

Тесты состоят из четырёх групп.

Тесты 1--3, из условия, оцениваются в 0 баллов.
В тестах этой группы \(1 \le N \le 100\), \(1 \le M \le 100\), \(0 \le a_i \le 1\,000\), \(0 \le b_i \le 1\,000\), \(0 \le L \le 10^6\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы \(1 \le N \le 1\,000\), \(1 \le M \le 1\,000\), \(0 \le a_i \le 10^6\), \(0 \le b_i \le 10^6\), \(0 \le L \le 10^9\). Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
Offline-группа, \(1 \le N \le 10^5\), \(1 \le M \le 10^5\), \(0 \le a_i \le 10^6\), \(0 \le b_i \le 10^6\), \(0 \le L \le 10^9\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Некоторые тесты этой группы объединяются в подгруппы, тесты за каждую подгруппу ставятся только при прохождении всех тестов подгруппы.

Примеры

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

6 8 179
4 9 23 15 43 7
3 10 14 7 3 8 7 3

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

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

5 8 5
5 3 8 14 1
10 7 3 7 12 3 3 6

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

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

2 2 4
6 13
8 10

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

#3332

Дуэт на клавиатуре

Темы: [Алгоритмы на строках] [Конечные автоматы]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2010-2011, Заключительный этап, Тур 1, Задача C ]

В 2030 году Очень Известная Компания выпустила новую клавиатуру. Разработчики решили избавиться от всех ненужных кнопок и оставить только кнопки с первыми \(A\) буквами латинского алфавита. Новая клавиатура пользуется большой популярностью, поэтому Петя решил научиться печатать на ней свое любимое слово (оно не содержит букв, отличных от первых \(A\) букв латинского алфавита).

Петя считает, что он научился, когда на экране можно будет увидеть его любимое слово целиком (то есть найдется последовательность подряд идущих букв, образующих его любимое слово). Например, если Петино любимое слово - "apple", и на экране написано "pineappled", то любимое слово увидеть можно, а если на экране написано "mapplicе", то нельзя. Петя запустил текстовый редактор, и пытается, совершив как можно меньше нажатий на клавиши, добиться появления своего любимого слова.

У Пети есть друг Вася, который хочет, чтобы Петя, напротив, совершил как можно больше нажатий на клавиши - так он лучше научится. В любые моменты (как до того, как Петя начал набирать текст, так и между нажатиями Пети на клавиши) Вася может отпихивать Петю от клавиатуры и печатать на ней что угодно. При этом ни Петя, ни Вася не могут стирать уже напечатанные символы. Суммарно Вася может сделать не более \(K\) нажатий на клавиши (не обязательно подряд), после этого Петя выгонит его из комнаты, и Вася больше никак не будет участвовать в процессе обучения.

Друзья видят, что написано на экране, и знают, сколько клавиш уже нажал каждый из них. Исходя из этого и Петя, и Вася действуют наиболее оптимально.

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

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

В первой строке входного файла содержатся три целых числа: \(N\), \(A\), \(K\) - длина любимого слова Пети, количество кнопок на клавиатуре и максимальное количество нажатий кнопок Васей соответственно. В следующей строке содержится слово длины \(N\), состоящее из строчных латинских букв - любимое слово Пети. Слово завершает перевод строки.

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

Выведите одно число - искомое количество нажатий клавиш.

Примечания

Тесты состоят из четырёх групп.

Тесты 1--3, из условия, оцениваются в 0 баллов.
В тестах этой группы \(1 \le N < A \le 26\), \(1 \le K \le 100\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы (при этом прохождения всех тестов из условия не требуется).
В тестах этой группы \(1 \le N \le 300\), \(1 \le A \le 26\), \(1 \le K \le 300\). Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
Offline-группа, \(1 \le N \le 100\,000\), \(1 \le A \le 26\), \(1 \le K \le 10^9\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Эта группа оценивается в 40 баллов, они начисляются только при прохождении всех тестов группы.

Примеры

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

2 1 2
aa

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

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

3 4 3
abc

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

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

3 2 1
aab

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