--->
10 задач
<---
Источники
#113251
Темы:
[Декартово дерево]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Петрик и Василько — настоящие друзья, поэтому они постоянно задают друг другу всевозможные интересные задачи. Однако Василько всегда с легкостью решает задачи своего друга, поэтому Петрик решил придумать по-настоящему сложную задачу. И вот что у него получилось. Будем называть число b подчислом числа a , если из числа a можно вычеркнуть некоторые цифры так, что цифры, которые остались, образуют число b . Задано n -цифровое число x . Обозначим как x k наибольшее k -цифровое подчисло числа x . Необходимо ответить на m запросов. Каждый запрос состоит из двух цифр - k и l . Ответом на запрос является l -я цифра числа x k . На этот раз задача действительно заставила Василько задуматься. А сможете ли вы решить ее быстрее его?
Входные данные
В первой строке входного файла содержится целое число x длины n ( 1 ≤ n ≤ 100 000 ). Во второй строке содержится число m ( 1 ≤ m ≤ 50 000 ). В следующих m строках содержится по два числа k i , l i ( 1 ≤ k i ≤ n , 1 ≤ l i ≤ k i ) — параметры i -го запроса.
Выходные данные
Выходной файл должен содержать одну строку длины m , i -й символ которого является ответом на i -й запрос.
Примечание
- n = 20, m = 10 000 .( 15 баллов)
- n · m ≤ 500 000 .( 25 баллов)
- n ≤ 100 000, m ≤ 50 000 .( 60 баллов)
Примеры
Входные данные
31415926 7 2 2 3 1 1 1 4 3 5 2 8 2 7 3
Выходные данные
6992511
#113581
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
Вам дан массив целых чисел длины N . Пусть s 1 , s 2 , ... , s q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.
Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 N - 1 .
Массив A лексикографически меньше массива B , если A i < B i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .
Определим хеш массива s , состоящего из элементов v 1 , v 2 , ... , v p , как: h ( s ) = ( v 1 · B p - 1 + v 2 · B p - 2 + ... + v p - 1 · B + v p ) mod M , где B и M - данные числа.
Посчитайте h ( s 1 ) , h ( s 2 ) , ... , h ( s K ) для данного K .
Входные данные
В первой строке содержатся числа N , K , B , M ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 100000 , 1 ≤ B , M ≤ 1000000 ).
Во второй строке содержится N чисел a 1 , a 2 , a 3 , ... , a N ( 1 ≤ a i ≤ 100000 ).
Гарантируется, что во всех тестах K ≤ 2 N - 1 .
Выходные данные
Выведите K строк, j -я строка должна содержать h ( s j ) и длину s j .
Примечание
Решения, работающие при 1 ≤ a 1 , a 2 , ..., a N ≤ 30 , будут оцениваться в 60 баллов.
Примеры
Входные данные
2 3 1 5 1 2
Выходные данные
1 1 3 2 2 1
Входные данные
3 4 2 3 1 3 1
Выходные данные
1 1 1 1 0 2 2 2
Входные данные
5 6 23 1000 1 2 4 2 3
Выходные данные
1 1 25 2 25 2 577 3 274 4 578 3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В рамках новой рекламной кампании некоторая корпорация хочет разместить свой логотип где-нибудь в городе. Компания собирается потратить весь рекламный бюджет на логотип, поэтому он должен быть воистину огромным. Один из менеджеров решил использовать здания целиком как части логотипа.
Логотип состоит из \(n\) вертикальных полос различной высоты. Полосы пронумерованы от \(1\) до \(n\) слева направо. Логотип описывается перестановкой \((s_1, s_2, ..., s_n)\) чисел \(1, 2, ..., n\). Полоса с номером \(s_1\) - самая низкая, полоса с номером \(s_2\) - следующая по высоте и, наконец, полоса \(s_n\) - самая высокая. Фактическая высота полос не имеет большого значения. Вдоль главной улицы расположено \(m\) зданий. К вашему удивлению, высота зданий различна. Задача состоит в том, чтобы найти все позиции, на которых логотип соответствует зданиям. Помогите компании и найдите все непрерывные последовательности зданий, которые соответствуют логотипу. Непрерывная последовательность зданий соответствует логотипу, если здание \(s_1\) в этой последовательности является самым низким, здание \(s_2\) является следующим по высоте и т. д. Например, последовательность зданий высотой \(5, 10, 4\) соответствует логотипу, описанному перестановкой \((3, 1, 2)\), поскольку здание №3 (высотой 4) является самым низким, здание №1 - вторым по высоте, а здание №2 - самым высоким.
Входные данные
Первая строка стандартного ввода содержит два целых числа \(n\) и \(m\) \((2 \le n \le m \le 1 000 000)\).
Вторая строка содержит \(n\) целых чисел \(s_i\), образующих перестановку чисел \(1, 2, ..., n\). То есть \(1 \le s_i \le n\) и s\(_i \neq s_j\) для \(i \neq j\).
Третья строка содержит \(m\) целых чисел \(h_i\) - высоты зданий (\(1 \le h_i \le 10^9\) для \(1 \le i \le m\)). Все числа различные.
В каждой строке числа разделены пробелами.
Выходные данные
Первая строка стандартного вывода должна содержать целое число \(k\) – количество совпадений.
Вторая строка должна содержать \(k\) целых чисел - индексы зданий начиная с 1, которые соответствуют первой полосе из логотипа в правильном соответствии. Числа должны быть перечислены в возрастающем порядке.
Если \(k = 0\), ваша программа должна напечатать пустую вторую строку.
Система оценки
В тестах суммарной стоимостью не менее 35 баллов \(n \le 5000\) и \(m \le 20 000\).
В тестах суммарной стоимостью не менее 60 баллов \(n \le 50 000\) и \(m \le 200 000\).
Примеры
Входные данные
5 10 2 1 5 3 4 5 6 3 8 12 7 1 10 11 9
Выходные данные
2 2 6
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
\(N\) субмарин бороздят просторы океана. Они расположены в ряд с первой по \(N\)-ю, расстояние между соседними по горизонтали \(5 км\). Они плывут в одну сторону в этом же порядке (впереди - первая) с одинаковыми постоянными скоростями, каждая на своей глубине. Каждая может послать сигнал, который получит ближайшая (по евклидову расстоянию на плоскости) из плывущих сзади, которая расположена глубже лодки, посылающей сигнал, если такая есть, и никто больше.
Происходят 2 вида событий:
"Поменять две соседних субмарины местами" - в нем указывается число \(i\) - номер одной из них, другая имеет номер \(i+1\). Действие происходит мгновенно, субмарины остаются на своих же глубинах.
"Отправить сигнал" – каждая субмарина отправляет сигнал.
Напишите программу, которая для каждого события второго типа посчитает, сколько максимум сигналов получила одна субмарина.
Входные данные
В первой строчке даны натуральные \(N\) и \(M\), разделённые пробелом.
Во второй строчке через пробел даны \(N\) натуральных ненулевых чисел, не превышающих \(3 000 000\) - глубины субмарин в миллиметрах порядке следования подводных лодок \(x\).
На каждой из следующих \(M\) строк дано по одному целому неотрицательному чиислу. Если это \(0\), то это действие первого типа, все издают сигнал; если это \(i>0\), то это значит, что субмарины \(i\) и \(i+1\) должны поменяться местами.
Выходные данные
Для каждого события отправки сигналов субмаринами выведите в отдельной строке ответ – максимальное количество сигналов, которые получит одна из субмарин за это действие.
Система оценки
1. (20 баллов) \(1 < N\leq 1000\), \(1\leq M\leq 100\).
2. (30 баллов) \(1 < N\leq 1000000\), \(1\leq M\leq 20\).
3. (50 баллов) \(1 < N\leq 1000000\), \(1\leq M\leq 100000\).
Примечание
Мы считаем субмарины точками.
Заметим, что субмарина, которая должна получить сигнал по описанию, при заданных горизонтальных расстояниях между лодками и возможными глубинами всегда не более, чем одна.
Примеры
Входные данные
9 3 100 300 50 1000 1100 1200 500 400 600 0 1 0
Выходные данные
2 3
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
Генная инженерия это весело. Ученые собрали несколько ДНК и хотят создать из них что-то новое. Каждая ДНК может быть представлена в виде последовательности оснований \(A\), \(G\), \(T\), \(C\). Обозначим за \(DNA[a:b]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и заканчивающийся в индексе \(b\), и за \(DNA[a..]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и идущий до конца последовательности. Ученые хотят производить следующие операции над последовательностью ДНК:
- Операция скрещивания: ученые берут два ДНК \(DNA_1\) и \(DNA_2\) и числа \(k_1\) и \(k_2\). После этого они создают два новых ДНК: \(DNA_3 = DNA_1[1..k1] + DNA_2[k2+1..]\) и \(DNA_4 = DNA_2[1..k_2] + DNA_1[k_1+1..]\).
- Операция мутации – они берут ДНК, число \(k\) и одно из оснований. После этого они заменяют основание в позиции \(k\) выбранного ДНК на новое основание.
- Также иногда ученым интересно получать статистику о своих ДНК. Для этого они применяют операцию подсчёта – они берут ДНК и числа \(k_1\) и \(k_2\) (\(k_1 \le k_2\)). Они хотят узнавать количества оснований \(A\), \(G\), \(T\), \(C\) в \(DNA[k_1..k_2]\).
Исходные ДНК нумеруются от \(1\) до \(n\) где \(n\) - количество индексов. При создание новых ДНК они занимают два минимальных неиспользуемых натуральных индекса.
Входные данные
В первой строке содержится единственное число \(n\) (1 <= n <= 20) – количество исходных ДНК.
В последующих \(n\) строках содержится описание каждого ДНК – строка \(s_i\) состоящая из символов \(A\), \(G\), \(T\), \(C\) обозначающая \(i\)-е ДНК.
В следующей строке содержится единственное число \(q\) (1 <= q <= 30000)– количество операций, которые нужно выполнить.
В последующих \(q\) строках содержится описание операций, которые необходимо выполнить. Описание каждой операции задаётся в следующем форматe:
CROSS \(id_1\) \(id_2\) \(k_1\) \(k_2\), \(id_1\) != \(id_2\)
MUTATE \(id\) \(k\) \(m\)
COUNT \(id\) \(k_1\) \(k_2\)
\(id\) - индекс некоторого ДНК.
Длина каждой исходной ДНК не превышает 30000. Сумма длин ДНК, образованных в результате перекрестной операции, не будет превышать 2000000000. Общее количество ДНК не будет превышать 10000. Гарантируется, что все операции правильные.
Выходные данные
Для каждой операции подсчёта выведите 4 числа: количества оснований \(A\), \(G\), \(T\), \(C\) соответсвенно в выбранном подотрезке данного ДНК.
Система оценки
Группа 0: Тест 1. 0 баллов
Группа 1: Тесты 2-6. 15 баллов. Дополнительные ограничения: длина любой ДНК не превосходит 1000. Для прохождения нужна группа 0
Группа 2: Тесты 7-11. 13 баллов. Дополнительные ограничения: Для всех запросов CROSS \(k_1\) = \(k_2\). Для прохождения нужна группа 1
Группа 3: Тесты 12-16. 23 балла. Дополнительные ограничения: отсутствует запрос MUTATE. Для прохождения нужна группа 1
Группа 4: Тесты 17-21. 14 баллов. Дополнительные ограничения: q <= 10000. Для прохождения нужны группы 2 и 3.
Группа 5: Тесты 22-26: 35 баллов. Дополнительных ограничений нет. Для прохождения нужна группа 4
Примеры
Входные данные
2 CTCGC TGCGG 5 MUTATE 1 2 A COUNT 2 2 4 MUTATE 2 1 G CROSS 2 1 1 5 COUNT 4 3 6
Выходные данные
0 2 0 1 0 2 0 2
Выбрано
:
|