Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 50 51 52 53 54 55 56 >> Отображать по:
#114134
Суровый корректор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

По мнению Александра Павловича, текст необычайно красив, если некоторые особые слова (например, «коммунизм», «Ленин», «счастье») встречаются не слишком часто, но и не слишком редко, к тому же достаточно равномерно.

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

В связи со своими воззрениями о красоте Александру Павловичу постоянно приходится проверять, сколько особых слов сейчас в той или иной части текста.

Он настолько устал от рутинного подсчёта: «а сколько тут особых слов?», «а сколько тут?», что просит вас помочь ему автоматизировать этот процесс.

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

Первая строка входного файла содержит текст длины \(L\) (\(1 \leq L \leq 10^5\)), в котором ищутся особые слова.

Следующая строка содержит \(N\) (\(1 \le n \le 10^5\)) — количество особых слов.

Следующие \(n\) строк содержат особые слова. Все особые слова различны. Суммарная длина строк не превосходит \(10^5\).

В следующей строке дано \(Q\) (\(1 \le q \le 10^5\)) — количество интересных Александру Павловичу отрезков.

Следующие \(q\) строк содержат сами отрезки.

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

Выведите \(q\) чисел — количества вхождений особых слов в соответствующий отрезок текста.

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

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

Обозначим за \(LEN_{max}\) максимальную длину особого слова.

  1. \(n \leq 1000, q = 1\), группа оценивается в \(11\) баллов.
  2. \(LEN_{max} \leq 1000, q = 1\), группа оценивается в \(13\) баллов.
  3. \(q = 1\), группа оценивается в \(12\) баллов. Группа зависит от 1, 2.
  4. \(n \leq 1000, q \leq 10000\), группа оценивается в \(21\) балл. Группа зависит от 1.
  5. \(LEN_{max} \leq 1000, q \leq 10000\), группа оценивается в \(19\) баллов. Группа зависит от 2.
  6. \(q \leq 10000\), группа оценивается в \(23\) балла. Группа зависит от 1, 2, 3, 4, 5.
  7. полные ограничения, группа оценивается в \(1\) балл. Группа зависит от 1, 2, 3, 4, 5, 6.
Примеры
Входные данные
abacababa
2
a
aba
3
5 9
2 2
2 6
Выходные данные
5 0 2
#114217
Винни-Пух и бочки меда
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

У Винни-Пуха есть \(n\) бочек меда. В \(i\)-й бочке налито \(a_i\) меда, а объем бочки равен \(b_i\) (\(1 \le i \le n\)). Винни-Пух хочет полностью заполнить все свои бочки. Для этого он последовательно делает \(q\) шагов. На \(j\)-м шаге он будет наливать мед в бочки с номерами от \(l_j\) до \(r_j\) (\(1 \le j \le q\)). В бочку с номером \(l_j\) Винни-Пух нальет \(c_j\) меда, в следующую бочку он нальет \(c_j + d_j\) меда, в следующую \(c_j + 2 \cdot d_j\) меда и так далее до бочки с номером \(r_j\).

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

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

В первой строке даны два целых числа \(n\) и \(q\) (\(1 \le n, \ q \le 2 \cdot 10^5\)).

Во второй строке через пробел даны \(n\) целых чисел \(0 \le a_1, \ldots, a_n \le 10^5\).

В третьей строке через пробел даны \(n\) целых чисел \(1 \le b_1, \ldots, b_n \le 10^9\).

В следующих \(q\) строках даны по четыре целых числа \(l_j\), \(r_j\), \(c_j\), \(d_j\) (\(1 \le l_j \le r_j \le n\), \(0 \le c_j, \ d_j \le 10^5\), \(1 \le j \le q\)).

Гарантируется, что \(a_i < b_i\) для всех \(1 \le i \le n\).

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

В единственной строке выведите \(n\) целых чисел -- ответ для каждой из бочек.

Примеры
Входные данные
5 3
0 0 0 0 2
7 7 7 7 7
1 5 1 1
2 5 1 1
1 3 4 0
Выходные данные
0 3 3 2 1
#114218
Бар у Мо
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

В баре у Мо дела идут как всегда прекрасно. Чтобы дела шли еще лучше, Мо озадачился вопросом разнообразия сортов пива, которые разливают в его баре. Для составления стратегического плана по улучшению списка сортов пива Мо должен получить ответы на ряд вопросов.

В данный момент у барной стойки сидят \(n\) посетителей и у каждого посетителя есть кружка с пивом одного из сортов. Мо пронумеровал посетителей слева направо числами от \(1\) до \(n\). После этого он пронумеровал сорта пива числами от \(1\) до \(m\). Далее Мо вспомнил число \(k\), которое было рекомендовано в гороскопе на эту неделю. Наконец, Мо составил список из \(q\) вопросов, ответы на которые помогут его бизнесу стать еще успешней. В каждом вопросе спрашивается следующее: каково количество сортов пива, которые можно встретить ровно \(k\) раз в кружках посетителей с номерами от \(l\) до \(r\) включительно.

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

В первой строке даны четыре целых числа \(n\), \(m\), \(q\) и \(k\) (\(1 \le n, \ q \le 2 \cdot 10^5\), \(1 \le m \le 10^6\), \(0 \le k \le 3\)).

Во второй строке даны \(n\) целых чисел \(1 \le a_1, \ldots, a_n \le m\) -- номера сортов пива у посетителей.

В следующих \(q\) строках заданы по два целых числа \(l\) и \(r\), которые задают запрос для посетителей с номерами от \(l\) до \(r\) (\(1 \le l \le r \le n\)).

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

Для каждого запроса выведите в отдельной строке количество сортов пива, которые на отрезке от \(l\) до \(r\) встречаются ровно \(k\) раз.

Примеры
Входные данные
5 5 2 2
1 2 2 1 5
1 5
2 4
Выходные данные
2
1
#114219
Бар у Мо 2
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes

В баре у Мо дела идут по-прежнему прекрасно. Как известно, чтобы дела шли еще лучше, Мо озадачился вопросом разнообразия сортов пива, которые разливают в его баре. Для составления стратегического плана по улучшению списка сортов пива Мо должен получить ответы на ряд вопросов.

В данный момент у барной стойки сидят \(n\) посетителей и у каждого посетителя есть кружка с пивом одного из сортов. Мо пронумеровал посетителей слева направо числами от \(1\) до \(n\). После этого он пронумеровал сорта пива числами от \(1\) до \(m\). Далее Мо вспомнил число \(k\), которое было рекомендовано в гороскопе на эту неделю. Наконец, Мо составил список вопросов, ответы на которые помогут его бизнесу стать еще успешней. В каждом вопросе спрашивается следующее: каково количество сортов пива, которые можно встретить ровно \(k\) раз в кружках посетителей с номерами от \(l\) до \(r\) включительно.

Мо ответил на все вопросы, но вдруг заметил, что пока он отвечал на вопросы, некоторые посетители выпивали свое пиво и тут же заказывали новую кружку с пивом, возможно другого сорта.

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

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

В первой строке даны четыре целых числа \(n\), \(m\), \(q\) и \(k\) (\(1 \le n, \ q \le 10^5\), \(1 \le m \le 10^6\), \(0 \le k \le 3\)).

Во второй строке даны \(n\) целых чисел \(1 \le a_1, \ldots, a_n \le m\) -- номера сортов пива у посетителей.

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

\(1 \ l \ r\) -- вопрос от Мо (\(1 \le l \le r \le n\)).

\(2 \ i \ j\) -- \(i\)-й посетитель перешел на пиво сорта \(j\), (\(1 \le i \le n\), \(1 \le j \le m\)).

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

Для каждого запроса первого типа выведите в отдельной строке ответ на него.

Примеры
Входные данные
5 5 3 2
1 2 2 1 5
1 1 5
2 3 3
1 1 5
Выходные данные
2
1
#114308
K-й элемент
  
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
256 megabytes

Дан массив чисел и натуральное число \(K\). Над ним проделывают следующую операцию: выбирают числа, стоящие на позициях, кратных \(K\) (т.е. на позициях \(0\), \(K\), \(2K\) и т.д.), находят максимальное среди них число и удаляют его из исходного массива. Если максимумов несколько, то выбирают первый из них. После удаления все числа, стоящие правее него, смещаются на одну позицию влево. Операцию повторяют, пока все числа не кончатся.

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

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

Первая строка содержит натуральные числа \(N\) и \(K\) \((2 \le K \le N \le 100000)\).

Вторая строка содержит \(N\) натуральных чисел из отрезка \([1, N]\).

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

Выведите \(N\) натуральных чисел, \(i\)-е из которых равно числу, удалённому на \(i\)-м шаге.

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

В задаче 5 подгрупп:

  • (7 баллов) Ограничения: \(N \le 1000\)
  • (25 баллов) Ограничения: \(K = 2\)
  • (23 балла) Ограничения: \(K \le 10\)
  • (25 баллов) Ограничения: \(100 \le K \le N\)
  • (20 баллов) Без дополнительных ограничений.

Примеры
Входные данные
10 2
2 3 1 9 10 4 5 6 1 5
Выходные данные
10
6
4
5
2
9
3
5
1
1
Входные данные
10 3
2 3 1 9 10 4 5 6 1 5
Выходные данные
9
10
4
5
6
2
5
3
1
1
Страница: << 50 51 52 53 54 55 56 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест