Структуры данных

128 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Subsequences Summing to Sevens#90389
\(N\) коров Фермера Джона выстроены в ряд. Каждая корова помечена различным целым числом - идентификатором. ФД хочет сделать фото непрерывной группы коров, но он делает фотографию группы коров, только если сумма их идентификаторов делится на 7.

Помогите ФД определить размер наибольшей группы коров, которую он сможет сфотографировать.

ФОРМАТ ВВОДА (файл div7.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)). Каждая из следующих \(N\) строк содержит идентификатор коровы (все в интервале \(0 \ldots 1,000,000\)).

ФОРМАТЫ ВЫВОДА (файл div7.out):

Выведите количество коров в наибольшей непрерывной группе коров, такой что сумма их идентификаторов делится на 7. Если такой группы нет, выведите 0.

Сумма может не поместится в 32-битное целое, Вы можете использовать 64-битное целое ("long long" в C/C++).

Префиксные суммы(минимумы, ...)
—Войти и решать
Fort Moo#90384
Беси строит форт прямоугольной формы.

Она уже выбрала место - кусок земли \(N\) метров по \(M\) метров (\(1 \leq N, M \leq 200\)). К несчастью, на этом месте есть болотистые участки, на которых строительство невозможно. Помогите Беси определить наибольшую (по площади) область, на которой можно построить форт, так , чтобы форт не проходил через болотистые участки.

ФОРМАТ ВВОДА (файл fortmoo.in):

Строка 1 содержит целые числа \(N\) и \(M\).

Следующие \(N\) строк содержат по \(M\) символов, формируя решётку, описывающую выбранное место. Символ '.' представляет траву, а символ 'X' представляет болотистую местность.

ФОРМАТ ВЫВОДА (файл fortmoo.out):

Единственное целое число, представляющее максимальную площадь, которую Беси может покрыть своим фортом.

Задачи на моделированиеПрефиксные суммы(минимумы, ...)
—Войти и решать
Cities and States#90365
Фермер Джон повесил большую карту США на стене своей фермы. Разглядывая её подолгу, коровы начали замечать курьезы. Например города Flint, MI и Miami, FL: первые две буквы первого города (Flint) дают код штата FL для второго города и наоборот, первые две буквы второго города (Miami) дают код штата первого города - MI.

Давайте назовём два города "специальной парой", если они удовлетворяют этому свойству и принадлежат разным штатам. Коровам интересно сколько всего существует "специальных пар". Помогите им!

ФОРМАТ ВВОДА (файл citystate.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 200,000\)), количество городов на карте.

Каждая из следующих \(N\) строк содержит две строки: имя города (от 2 до 10 маленьких латинских букв) и двухсимвольный код штата (из больших латинских букв). Заметим, что код штата может быть например ZQ, хотя в действительности в США нет такого штата. Могут существовать города с одинаковыми названиями, но они будут в различных штатах.

ФОРМАТ ВЫВОДА (файл citystate.out):

Выведите количество специальных пар городов.

реализацияХеш
—Войти и решать
Breed Counting#90353
\(N\) коров Фермера Джона, последовательно пронумерованных от \(1 \ldots N\), выстроены в ряд. Каждая корова имеет ID породы: 1 - Holsteins, 2 - Guernseys, 3 - Jerseys. ФД просит Вас посчитать количество коров каждой породы, внутри некоторого интервала этого порядка.

ФОРМАТ ВВОДА (файл bcount.in):

Первая строка ввода содержит \(N\) и \(Q\) (\(1 \leq N \leq 100,000\), \(1 \leq Q \leq 100,000\)).

Следующие \(N\) строк содержат целое число 1,2, или 3 - ID породы соответствующей коровы.

Следующиеt \(Q\) строк описывают запрос в виде двух целых чисел \(a, b\) (\(a \leq b\)).

ФОРМАТ ВЫВОДА (файл bcount.out):

Для каждого из \(Q\) запросов \((a,b)\), выведите строку, содержащую три целых числа количество коров в интервале \(a \ldots b\), имеющих номера пород 1,2,3.

Префиксные суммы(минимумы, ...)
—Войти и решать
Counting Haybales#90344

Ферма Джона состоит из \(N\) полей в ряд последовательно пронумерованных \(1 \ldots N\). На каждом поле может быть произвольное количество стогов сена. Инструкции ФД бывают трёх видов:

1) Добавить один стог к каждому полю в указанном интервале

2) Определить минимальное количество стогов сена внутри указанного непрерывного интервала полей.

3) Посчитать суммарное количество стогов сена внутри указанного непрерывного интервала.

ФОРМАТ ВВОДА (файл haybales.in):

Первая строка содержит два положительных целых числа \(N\) (\(1 \leq N \leq 200,000\)) и \(Q\) (\(1 \leq Q \leq 100,000\)).

Следующая строка содержит \(N\) неотрицательных целых чисел, каждое не более, чем 100,000, указывающих, сколько стогов сена было изначально на каждом поле.

Каждая из следующих \(Q\) строк содержит одну большую латинскую букву M, P или S, за которой следуют два положительных целых числа \(A\) and \(B\) (\(1 \leq A \leq B \leq N\)), или три положительных целых числа \(A\), \(B\), and \(C\) (\(1 \leq A \leq B \leq N\); \(1 \leq C \leq 100,000\)). 3 числа будет только в том случае, если первая буква P.

Если первая буква M выведите минимальное количество стогов сена в интервале полей \(A \ldots B\).

Если первая буква P, добавьте по \(C\) стогов сена в каждое поле в интервале \(A \ldots B\).

Если первая буква S, выведите суммарное количество стогов сена в интервале полей \(A \ldots B\).

ФОРМАТ ВЫВОДА (файл haybales.out):

Строка в выводе должна появится в ответ на каждый запрос вида M или S.

Дерево отрезков, RSQ, RMQ
—Войти и решать
Breed Counting#90342
\(N\) коров Фермера Джона, последовательно пронумерованных от \(1 \ldots N\), выстроены в ряд. Каждая корова имеет ID породы: 1 - Holsteins, 2 - Guernseys, 3 - Jerseys. ФД просит Вас посчитать количество коров каждой породы, внутри некоторого интервала этого порядка.

ФОРМАТ ВВОДА (файл bcount.in):

Первая строка ввода содержит \(N\) и \(Q\) (\(1 \leq N \leq 100,000\), \(1 \leq Q \leq 100,000\)).

Следующие \(N\) строк содержат целое число 1,2, или 3 - ID породы соответствующей коровы.

Следующиеt \(Q\) строк описывают запрос в виде двух целых чисел \(a, b\) (\(a \leq b\)).

ФОРМАТ ВЫВОДА (файл bcount.out):

Для каждого из \(Q\) запросов \((a,b)\), выведите строку, содержащую три целых числа количество коров в интервале \(a \ldots b\), имеющих номера пород 1,2,3.

Префиксные суммы(минимумы, ...)
—Войти и решать
Marathon#90331

Беси спланировала марафон, специфицировав N контрольных точек
(1 <= N <= 100,000), которые нужно последовательно посетить.

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

Для того чтобы построить наилучший маршрут Беси хочет исследовать
последствия выполнения изменений в месторасположения контрольных точек
её текущего маршрута. Помогите ей определить, как определённые изменения
расположения контрольных точек влияют на время, требуемое для прохождения
различных подмаршрутов (принимая во внимание, что коровы могут выбрать
пропуск одной контрольной точки во время пробега по подмаршруту).

Поскольку марафон проходит на улицах Манхэттена, расстояние между двумя
контрольными точками с координатами (x1, y1) и (x2, y2) надо вычислять
как манхэттенское: |x1-x2| + |y1-y2|.

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

В первой стоке хадаются N и Q (1 <= Q <= 100,000).
Последующие N строк содержат (x,y)- положение N контрольных точек в порядке
их посещения вдоль маршрута. Все координаты в интервале -1000 .. 1000.
Последующие Q строк состоят из изменений и запросов по одному в строке,
которые необходимо обрабатывать в том порядке, в котором они заданы.
Эти строки имеют вид "U I X Y" или "Q I J".

Строка в форме "U I X Y" указывает, что местоположение точки с номером
I (1 <= I <= N) должно быть изменено на (X Y).

Строка в форме "Q I J" спрашивает минимальное время прохождения подмаршрута
от контрольной точки I до контрольной точки J (I<=J), с учётом того, что
коровы могут выбрать пропустить одну контрольную точку вдоль этого подмаршрута
(кроме точек I и J).

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

Для каждого подмаршрута выведите требуемую длину на отдельной строке.

Префиксные суммы(минимумы, ...)
—Войти и решать
Marathon#90328

Фермер Джон отправил Беси на марафон.
Дистанция включает N (3 <= N <= 100,000) контрольных пунктов,
которые нужно посетить поочерёдно, от 1 до N.
Ленивая Беси решила пропустить один контрольный пункт
(не 1 и не N разумеется).

Помогите Беси найти минимальное расстояние, которое ей придётся
пробежать, если она пропустит один контрольный пункт.

Замечание: расстояние между двумя точками (x1,y1) и (x2,y2)
надо рассматривать и вычислять как манхэттенское
|x1-x2| + |y1-y2|,
поскольку во время этого марафона двигаться можно только
параллельно осям координат.

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

Первая строка даёт значение N.

Каждая из последующих N строк содержит два разделённых
пробелом целых числа X и Y (-1000 <= x <= 1000, -1000 <= y <= 1000),
представляющих контрольный пункт.

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

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

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

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

Выведите минимальное расстояние, которое пробежит Беси, пропустив
один контрольный пункт. Не забудьте вывести перевод на новую строку.

В приведенном примере, пропустив точку(8,3) получим
минимальное расстояние 14.

Пример вывода

14

Задача на реализациюПрефиксные суммы(минимумы, ...)
—Войти и решать
Farmer John's Favorite Operation#90311

У Фермера Джона есть массив \(a\) из \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) неотрицательных целых чисел и целое число \(M\) (\(1 \leq M \leq 10^9\)). Затем ФД спрашивает у Беси число \(x\). За одну операцию ФД может выбрать индекс \(i\) и вычесть или прибавить \(1\) к \(a_i\). ФД называет число скучным - если оно равно минимальному количеству операций, которые он должен выполнить, чтобы \(a_i-x\) стало делится на \(M\) для всех \(1 \leq i \leq N\).

Среди всех возможных \(x\) выберите минимально возможное скучное число.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(T\) (\(1 \leq T \leq 10\)), количество независимых подтестов.

Первая строка каждого подтеста содержит числа \(N\) и \(M\).

Вторая строка каждого подтеста содержит \(a_1, a_2, ..., a_N\) (\(0 \leq a_i \leq 10^9\)).

Гарантируется, что сумма \(N\) по всем подтестам не превысит \(5 \cdot 10^5\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого подтеста выведите целое число - минимальное скучное число по всем возможным \(x\).

Префиксные суммы(минимумы, ...)сортировкитеория чисел
—Войти и решать
The Best Subsequence#90289
п»ї

У Фермера Джона есть двоичная строка длиной \(N\) \((1 \leq N \leq 10^9)\), изначально из одних нулей.

Сначала он выполнит \(M\) (\(1 \leq M \leq 2 \cdot 10^5\)) изменений строки по порядку. Каждое изменение переворачивает каждый символ от \(l\) до \(r\). То есть \(0\) изменяется на \(1\) и наоборот.

Затем он задаёт Вам \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) вопросов. Для каждого вопроса Вы должны ввести лексикографически наибольшую подпоследовательность длины \(k\) состоящую из символов подстроки от \(l\) до \(r\). Если Ваш ответ - двоичная строка \(s_1s_2 \dots s_k\), выведите \(\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}\) (то есть строка интерпретируется как двоичное число) по модулю \(10^9+7\).

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

Напомним, что строка \(A\) лексикографически больше чем строка \(B\) такой же длины если и только если в первой позиции \(i\), если она существует, \(A_i \neq B_i\), выполняется \(A_i > B_i\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\), \(M\), \(Q\).

Следующие \(M\) строк содержат по два целых числа \(l\) и \(r\) (\(1 \leq l \leq r \leq N\)) конечные точки обновления.

Следующие \(Q\) строк содержат по три целых числа, \(l\), \(r\), \(k\) (\(1 \leq l \leq r \leq N, 1 \leq k \leq r - l + 1\)) —

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(Q\) строк. \(i\)-ая строка должна содержать ответ на \(i\)-ый запрос.

ПР�МЕР ВВОДА:

5 3 9
1 5
2 4
3 3
1 5 5
1 5 4
1 5 3
1 5 2
1 5 1
2 5 4
2 5 3
2 5 2
2 5 1

ПР�МЕР ВЫВОДА:

21
13
7
3
1
5
5
3
1

После выполнения \(M\) операций, строка такова: \(10101\).

Для первого запроса - длины \(5\) ответ вся строка \(10101\), которая интерпретируется как \(1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21\).

Для второго запроса, существует \(5\) уникальных подпоследовательностей длины \(4\): \(0101\), \(1101\), \(1001\), \(1011\), \(1010\). Лексикографически наибольшая из них \(1101\), которая интерпретируется как \(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13\).

Для третьей строки лексикографически наибольшая последовательность \(111\), которая интерпретируется как \(7\).

ПР�МЕР ВВОДА:

9 1 1
7 9
1 8 8

ПР�МЕР ВЫВОДА:

3

ПР�МЕР ВВОДА:

30 1 1
1 30
1 30 30

ПР�МЕР ВЫВОДА:

73741816

Не забудьте выводить ответ по модулю \(10^9+7\).

ОЦЕН�ВАН�Е:

  • Тест 4: \(N \leq 10, Q \leq 1000\)
  • Тест 5: \(M \leq 10\)
  • Тесты 6-7: \(N, Q \leq 1000\)
  • Тесты 8-12: \(N \leq 2 \cdot 10^5\)
  • Тесты 13-20: Нет дополнительных ограничений.

Автор: Chongtian Ma

Дерево отрезков, RSQ, RMQ
—Войти и решать
Splitting Haybales#90280

Фермер Джон хочет справедливо разделить пакеты сена между его двумя любимыми коровами Беси и Эльза. У него есть \(N\) ( \(1\le N\le 2\cdot 10^5\)) пакетов сена, упорядоченных в невозрастающем порядке. Где \(i\)-ый пакет сена имеет \(a_i\) единиц сена ($2\cdot 10^5\ge a1\ge a2 \ge \dots \ge aN \ge 1$).

ФД хочет разделить непрерывный отрезок пакетов \(a_l, \dots, a_r\) между Беси и Эльзой, рассматривая пакеты в порядке от \(l\) до \(r\), и когда рассматривает \(i\)-ый пакет он даёт его корове, у которой сейчас меньше сена. Если равно - даёт Беси.

Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый описывается тремя целыми числами \(l,r,x\) (\(1\le l\le r\le N\), \(|x|\le 10^9\)). Для каждого запроса, введите на сколько больше единиц сена будет у Беси, после обработки пакетов от \(l\) до \(r\), если Беси начнёт с количеством сена на \(x\) единиц больше чем у Эльзы. Заметим эта величина отрицательна, если вначале у Эльзы будет на \(x\) единиц больше чем у Беси.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\).

Вторая строка содержит \(a_1\dots a_N\).

Третья строка содержит \(Q\).

Следующие \(Q\) строк содержат \(l, r, x\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(Q\) строк, содержащих ответ на каждый запрос.

Префиксные суммы(минимумы, ...)
—Войти и решать
Identity Theft#90279

**Замечание: Время на тест и ограничение по памяти для этой задачи 3сек и 512MB, что, соответственно, в 1.5 и 2 раза больше чем по умолчанию.**

Каждая из \(N\) (\(1 \leq N \leq 10^5\)) коров Фермера Джона имеет свой ID-номер в виде битовой строки (строки соcтоящей из символов '0' и '1'). Беси, старейшая корова, помнит ID-номера всех коров и любит спрашивать у коров их ID-номера.

Когда у коровы спрашивают ID-номер, они начинают отвечать правильную битовую строку, но могут забыть и остановиться, не закончив её. Когда Беси слышит битовую строку, если та не является ID-номером ни одной коровы на ферме, она пожимает плечами и уходит. Однако если это ID-номер другой коровы на ферме, она предполагает, что произошла кража личных данных и закрывает ферму на карантин. Заметим, что это может случиться даже если корова говорит свой полный правильный ID-номер.

ФД хочет избавиться от последней ситуации и добавить несколько битов к некоторым ID-номерам. За одну секунду он может добавить один бит в конец ID-номера любой коровы. Определите минимальное количество времени, которое потребуется чтобы избежать карантина по совпадению правильного ID-номера.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\), количество коров на ферме у ФД.

Далее следуют \(N\) строк. \(k\)-я строка содержит битовую строку, равную ID-номеру \(k\)-ой коровы.

Никакой и ID-номеров не пустой, и общая длина всех ID-номеров не более \(10^6\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите минимальное количество секунд, которое требуется фермеру Джону чтобы обеспечить, что карантин не случится.

Бор
—Войти и решать
Grass Segments#90276

Беси посадила траву на положительной вещественной прямой. У неё есть \(N\) (\(2\le N\le 2\cdot 10^5\)) различных сортов травы. И она посадит траву \(i\)-го сорта на интервале \([\ell_i, r_i]\) (\(0 < \ell_i < r_i \leq 10^9\)).

Известно, что сорт \(i\) растёт лучше, если есть некоторый сорт \(j\) (\(j\neq i\)) такой, что сорт \(j\) и сорт \(i\) перекрываются на длину не менее \(k_i\) (\(0 < k_i \leq r_i - \ell_i\)). Беси хочет для каждого сорта \(i\) вычислить количество таких of \(j\neq i\), что сорты \(j\) и \(i\) перекрываются на длину не менее \(k_i\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит число \(N\).

Каждая из последующих \(N\) строк содержит три разделённых одиночными пробелами целых числа \(\ell_i\), \(r_i\), \(k_i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Ответы для всех сортов на отдельных строках.

SCORING:

  • Тесты 4-5: \(N \leq 5000\)
  • Тесты 6-11: \(k\) одинаковое для всех интервалов
  • Тесты 12-20: Нет дополнительных ограничений..

В дополнение, в тестах 5, 7, ..., 19, \(r_i \leq 2N\) for all \(i\).

Автор: Benjamin Qi

ОтрезкиПрефиксные суммы(минимумы, ...)Сортировка событий
—Войти и решать
Milk Sum#90233

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

\(N\) коров фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) имеют целую продуктивность \(a_1,\dots,a_N\). То есть \(i\)я корова производит \(a_i\) единиц молока за минуту ( \(0 \leq a_i \leq 10^8\)).

Каждое утро фермер Джон начинает с того, что все \(N\) коров подключены к его дойке. От него требуется отцеплять их по одной, отправляя прочь для их ежедневных упражнений. Первая корова, которую он отправляет, снимается с крючка после всего 1 минуты дойки, вторая корова, которую он отправляет, отцепляется после двух минут дойки и так далее. Поскольку первая корова (скажем, корова \(x\)) тратит только одну минуту на доильном аппарате она вносит только \(a_x\) единиц общего количества молока. Вторая корова (скажем, корова \(y\)) тратит на доение всего две минуты и, таким образом, дает \(2a_y\) единиц общего количества молока. Третья корова (скажем, корова \(z\)) приносит всего \(3a_z\) единиц и так далее. Пусть \(T\) представляет собой максимально возможное количество молока, которое может собрать фермер Джон, если он отцепляет своих коров в оптимальном порядке.

Фермеру Джону интересно, как повлияет на \(T\), если часть производительностей молока в его стаде были другими. Для каждого из запросов \(Q\) (\(1\le Q\le 1.5\cdot 10^5\)) каждое из которых задано двумя целыми числами \(i\) и \(j\), пожалуйста, рассчитайте, какой будет новое значение \(T\), если \(a_i\) было установлено в \(j\) (\(0 \leq j \leq 10^8\)). Обратите внимание, что каждый запрос рассматривает временное потенциальное изменение независимо от всех других запросов; то есть \(a_i\) возвращается к исходному значению перед следующим запросом.

ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):

Первая строка содержит \(N\).

Вторая строка содержит \(a_1\dots a_N\).

Третья строка содержит \(Q\).

Следующие \(Q\) строк содержат по два целых числа \(i\) и \(j\), разделенных пробелом.

ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):

Пожалуйста, выведите значение \(T\) для каждого из запросов \(Q\) в отдельных строках.

Использование сортировкиПрефиксные суммы(минимумы, ...)реализация
—Войти и решать
Pareidolia#90230

**Примечание. Ограничение по времени для этой задачи составляет 4 секунды, что в два раза больше, чем по умолчанию. Ограничение по памяти для этой задачи составляет 512 МБ, вдвое больше, чем по умолчанию.**

Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры, которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон постоянно находится рядом с коровами, он часто видит коровьи узоры в повседневных предметах. Например, если он смотрит на строка "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и все, что он видит, это «bessiebessie».

Дана строка \(s\), пусть \(B(s)\) представляет собой максимальное количество повторяющихся копий. из «bessie» можно получить, удалив ноль или более символов из \(s\). В приведенном выше примере \(B(\)"bqessiyexbesszieb"\() = 2\). Кроме того, учитывая строка \(t\), пусть \(A(t)\) представляет собой сумму \(B(s)\) по всем непрерывным подстроки \(s\) строки \(t\).

У фермера Джона есть строка \(t\) длины не более \(2\cdot 10^5\), состоящая только из символов a-z. Пожалуйста, рассчитайте \(A(t)\) и как \(A(t)\) изменится после \(U\) (\(1\le U\le 2\cdot 10^5\)) обновлений, каждое из которых изменяет символ \(t\). Обновления являются кумулятивными.

ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):

Первая строка ввода содержит \(t\).

Следующая строка содержит \(U\), за которыми следуют строки по \(U\), каждая из которых содержит позицию \(p\) (\(1\le p\le N\)) и символ \(c\) в диапазоне от a до z, что означает, что \(p\)-й символ \(t\) заменяется на \(c\).

ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):

Выведите \(U+1\) строк — общее количество «bessie», которое можно сделать во всех подстроках \(t\) перед любыми обновлениями и после каждого обновления.

Дерево отрезков, RSQ, RMQдпреализация
—Войти и решать
Haybale Distribution#90191

Фермер Джон развозит сено по ферме.

Ферма имеет \(N\) \((1\le N\le 2\cdot 10^5)\) амбаров, расположенных в целых точках \(x_1,\dots, x_N\) \((0 \le x_i \le 10^6)\) на числовой прямой. ФД запланировал \(N\) перевозок сена в некоторую целую точку \(y\) \((0 \le y \le 10^6)\) и затем одну перевозку к каждому амбару.

К несчастью служба доставки очень расточительна. В частности, для некоторых \(a_i\) и \(b_i\) \((1\le a_i, b_i\le 10^6)\), \(a_i\) пакетов сена теряются на единицу расстояния каждой доставки влево и \(b_i\) пакетов сена теряются на единицу расстояния каждой доставки вправо. Формально при транспортировке из точки \(y\) в амбар в точке \(x\), количество теряемых пакетов сена определяется как

\[\begin{cases} a_i\cdot (y-x) & \text{if } y \ge x \\ b_i\cdot (x-y) & \text{if } x > y \end{cases}.\]

Вам даны \(Q\) \((1\le Q\le 2\cdot 10^5)\) независимых запросов, каждый состоит из возможных значений \((a_i,b_i)\), помогите ФД определить наименьшее количество потерянных пакетов сена, если он выберет \(y\) оптимально.

ФОРМАТ ВВОДА (с клавиатуры):

Первая строка содержит \(N\).

Следующая строка содержит \(x_1\dots x_N\).

Следующая строка содержит \(Q\).

Каждая из последующих \(Q\) строк содержит два целых числа \(a_i\) и \(b_i\).

ФОРМАТ ВЫВОДА (на экран):

Выведите \(Q\) строк, \(i\)-ая строка содержит ответ на \(i\)-ый запрос.

Префиксные суммы(минимумы, ...)
—Войти и решать
Subset Equality#90185

Коровы передают две строки \(s\) и \(t\), каждая с длиной не более \(10^5\), состоящие только из маленьких латинских букв от 'a' до 'r'. Вы должны ответить на \(Q\) запросов (\(1 \leq Q \leq 10^5\)). Для каждого запроса нужно ответить, совпадут ли строки, если в каждой из них оставить только указанные в запросе маленькие латинские буквы (удалив все остальные символы).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(s\).

Вторая строка содержит \(t\).

Третья строка содержит \(Q\).

Каждая из последующих \(Q\) строк содержит строку запроса. В строке запроса символы не повторяются и задаются в алфавитном порядке. Никакой запрос не появляется более одного раза.

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого запроса выведите 'Y', если \(s\) и \(t\), с символами только из запроса будут равны и 'N' в противном случае.

Префиксные суммы(минимумы, ...)
—Войти и решать
Counting Liars#90175
Корова Беси прячется где-то на числовой прямой. Каждая из \(N\) (\(1\le N\le 1000\)) других коров Фермера Джона имеет информацию, которой она делится с ФД: \(i\)-ая корова говорит, что Беси прячется в некоторой точке меньше либо равной to \(p_i\), или больше либо равной \(p_i\), (\(0\le p_i\le 10^9\)).

К несчастью, возможна ситуация противоречивости ответов всех коров. Это означает, что не все коровы говорили правду. Вычислите минимальное количество коров, которые солгали.

ФОРМАТ ВВОДА (С КЛАВИАТУРЫ / stdin):

Первая строка содержит \(N\).

Каждая из следующих \(N\) строк содержит символ L или G, за которым следует целое число \(p_i\). L означает, что \(i\)-ая корова говорит, что Беси скрывается в позиции меньше либо равной \(p_i\), а G означает, что \(i\)-ая корова говорит, что Беси скрывается в позиции больше либо равной \(p_i\)

ФОРМАТ ВЫВОДА (на экран / stdout):

Минимальное количество коров, которые солгали.

Жадный алгоритмЗадачи на моделированиеПрефиксные суммы(минимумы, ...)
—Войти и решать
Sleeping in Class#90158
Беси радовалась введённому индивидуальному обучению. К несчастью её тьютор Фермер Джон очень скучный лектор, и поэтому она часто засыпала во время занятий.

ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии. Всего было \(N\) занятий (\(2\le N\le 10^5\)), и Эльза зафиксировала \(a_i\) (\(1\le a_i\le 10^{18}\)) засыпаний на \(i\)-ом занятии. Общее количество засыпаний на всех занятиях не превышает \(10^{18}\).

Эльза хочет представить дело так, что Беси засыпала одинаковое количество раз на каждом занятии.

Единственный способ Эльзы модифицировать свои записи - объединить два соседних занятия или разъединить одно занятие на два. Например, если \(a=[1,2,3,4,5],\) тогда если Эльза объединит второе и третье занятие, то лог станет \([1,5,4,5]\) Если Эльза выберет разделить третье занятие на два, то лог может стать одним из \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\), or \([1,5,4,0,5]\).

По заданным \(Q\) (\(1\le Q\le 10^5\)) кандидатам \(q_1,\ldots,q_Q\) для наименее любимых Беси чисел (\(1\le q_i\le 10^{18}\)), для каждого из них помогите Эльзе вычислить минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка каждого теста содержит \(N\), а вторая содержит \(a_1,a_2,\ldots,a_N\). Третья строка содержит \(Q\) - количество запросов, за которым следует \(Q\) строк с целым числом \(q_i\) - кандидат в наименее любимое число Беси.

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого \(q_i\) вычислите минимальное количество модификаций, которое требуется для Эльзы, чтобы конвертировать лог в \(q_i\) или выведите \(-1\), если это невозможно.

Жадный алгоритмЗадачи на моделированиеПрефиксные суммы(минимумы, ...)
—Войти и решать
Convoluted Intervals#90131
Коровы играют в игру со множеством из \(N\) интервалов (\(1\le N\le 2\cdot 10^5\)), где \(i\)-ый интервал начинается в позиции \(a_i\) на числовой прямой, а заканчивается в позиции \(b_i \geq a_i\). Оба числа \(a_i\) and \(b_i\) - целые, в интервале \(0 \ldots M\), где \(1 \leq M \leq 5000\).

Чтобы играть в эту игру, Беси выбирает некоторый интервал, например \(i\)-ый. И Эльза выбирает некоторый интервал, например, \(j\)-ый, возможно тот же самый. Для заданной величины \(k\) они выигрывают, если \(a_i + a_j \leq k \leq b_i + b_j\).

Для всех \(k\) в интервале \(0 \ldots 2M\), посчитайте количество упорядоченных пар \((i,j)\) для которых Беси и Эльза выиграют в эту игру.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка ввода содержит \(N\) и \(M\). Каждая из последующих \(N\) строк описывает интервал в терминах целых чисел \(a_i\) и \(b_i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(2M+1\) строку, по одной для каждого \(k\) в интервале \(0 \ldots 2M\).

Префиксные суммы(минимумы, ...)
—Войти и решать
Поделиться
Класснуть