Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 512 мегабайт
Реализуйте просто двоичное дерево поиска.
Входной файл содержит описание операций с деревом, их количество не превышает 100. В каж- дой строке находится одна из следующих операций:
-
insert x — добавить в дерево ключ x. Если ключxесть в дереве, то ничего делать не надо
-
delete x — удалить из дерева ключ x. Если ключаxв дереве нет, то ничего делать не надо
-
exists x — если ключ x есть в дереве выведите «true», если нет «false»
-
next x — выведите минимальный элемент в дереве, строго больший x, или «none» если такого нет
-
prev x — выведите максимальный элемент в дереве, строго меньший x, или «none» если такого нет
В дерево помещаются и извлекаются только целые числа, не превышающие по модулю 10^9.
Выведите последовательно результат выполнения всех операций exists,next,prev. Следуйте формату выходного файла из примера.
стандартный ввод
insert 2
insert 5
insert 3
exists 2
exists 4
next 4
prev 4
delete 5
next 4
prev 4стандартный вывод
true
false
5
3
none
3Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 512 мегабайт
Реализуйте сбалансированное двоичное дерево поиска.
Входной файл содержит описание операций с деревом, их количество не превышает 10^5. В каж- дой строке находится одна из следующих операций:
-
insert x — добавить в дерево ключ x. Если ключxесть в дереве, то ничего делать не надо
-
delete x — удалить из дерева ключ x. Если ключаxв дереве нет, то ничего делать не надо
-
exists x — если ключ x есть в дереве выведите «true», если нет «false»
-
next x — выведите минимальный элемент в дереве, строго больший x, или «none» если такого нет
-
prev x — выведите максимальный элемент в дереве, строго меньший x, или «none» если такого нет
В дерево помещаются и извлекаются только целые числа, не превышающие по модулю 10^9.
Выведите последовательно результат выполнения всех операций exists,next,prev. Следуйте формату выходного файла из примера.
стандартный ввод
insert 2
insert 5
insert 3
exists 2
exists 4
next 4
prev 4
delete 5
next 4
prev 4стандартный вывод
true
false
5
3
none
3
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Вам даны пары чисел (ai, bi). Необходимо построить декартово дерево, такое что i-я вершина имеет ключи (ai, bi), вершины с ключом ai образуют бинарное дерево поиска, а вершины с ключом bi образуют кучу.
В первой строке записано число N — количество пар. Далее следует N ( 1 ⩽ N ⩽ 300 000) пар (ai, bi). Для всех пар |ai|; |bi| ⩽ 30 000. ai̸=aj и bi̸=bj для всех i̸=j .
Если декартово дерево с таким набором ключей построить возможно, выведите в первой стро- ке «YES», в противном случае выведите «NO». В случае ответа «YES» выведите N строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номера предка, номера левого сына и номера правого сына. Если у вершины отсутствует предок или какой либо из сыновей, выведите на его месте число 0. Если подходящих деревьев несколько, выведите любое.
стандартный ввод
7
5 4
2 2
3 9
0 5
1 3
6 6
4 11
стандартный вывод
YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Вы работаете в компании Макрохард и вас попросили реализовать структуру данных, которая будет хранить множество целых ключей. Будем считать, что ключи хранятся в бесконечном массиве A, проиндексированном с 1 , исходно все его ячейки пусты. Структура данных должна поддерживать следующую операцию: Insert(L,K), где L — позиция в массиве, а K — некоторое положительное целое число. Операция должна выполняться следующим образом:
-
Если ячейка A[L] пуста, присвоить A[L] <- K.
-
Если A[L] непуста, выполнить Insert(L+ 1,A[L]) и затем присвоить A[L] <- K.
По заданным N целым числам L1, L2,...,LN выведите массив после выполнения последователь ности операций: Insert(L1 , 1 ) Insert(L2 , 2 ) ... Insert(LN,N)
Первая строка входного файла содержит числа N — количество операций Insert, которое следует выполнить и M — максимальную позицию, которая используется в операциях Insert ( 1 ⩽ N ⩽ 131 072, 1 ⩽ M ⩽ 131 072). Следующая строка содержит N целых чисел Li, которые описывают операции Insert, которые следует выполнить ( 1 ⩽ Li ⩽ M).
Выведите содержимое массива после выполнения всех сделанных операций Insert. На первой строке выведите W — номер максимальной непустой ячейки в массиве. Затем выведите W целых чисел — A[1], A[2],..., A[W]. Выводите нули для пустых ячеек.
стандартный ввод
5 4
3 3 4 1 3стандартный вывод
6
4 0 5 2 3 1Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мегабайт
Реализуйте структуру данных, которая поддерживает множество S целых чисел, с котором раз- решается производить следующие операции:
-
add(i)— добавить в множество S число i (если он там уже есть, то множество не меняется);
-
sum(l, r) — вывести сумму всех элементов x из S, которые удовлетворяют неравенству l ⩽ x ⩽ r.
Исходно множество S пусто. Первая строка входного файла содержит n — количество операций ( 1 ⩽ n ⩽ 300 000).Следующие n строк содержат операции. Каждая операция имеет вид либо «+i», либо «? l r». Операция «? l r» задает запрос sum(l, r). Если операция « +i » идет во входном файле в начале или после другой операции «+», то она задает операцию add(i). Если же она идет после запроса «?», и результат этого запроса былy, то выполняется операция add((i + y) mod 10^9 ). Во всех запросах и операциях добавления параметры лежат в интервале от 0 до 10^9.
Для каждого запроса выведите одно число — ответ на запрос.
стандартный ввод
6
+ 1
+ 3
+ 3
? 2 4
+ 1
? 2 4стандартный вывод
3
7Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 512 мегабайт
Напишите программу, реализующую структуру данных, позволяющую добавлять и удалять эле- менты, а также находить k-й максимум.
Первая строка входного файла содержит натуральное число n — количество команд (n ⩽ 100 000). Последующиеnстрок содержат по одной команде каждая. Команда записывается в виде двух чиселc i и ki — тип и аргумент команды соответственно (|ki| ⩽ 10^9 ). Поддерживаемые команды:
-
+1 (или просто 1 ): Добавить элемент с ключом ki.
-
0 : Найти и вывести ki-й максимум.
-
-1 : Удалить элемент с ключом ki.
Гарантируется, что в процессе работы в структуре не требуется хранить элементы с равными ключами или удалять несуществующие элементы. Также гарантируется, что при запросе ki-го мак- симума, он существует.
Для каждой команды нулевого типа в выходной файл должна быть выведена строка, содержа- щая единственное число — ki-й максимум.
стандартный ввод
11
+1 5
+1 3
+1 7
0 1
0 2
0 3
-1 5
+1 10
0 1
0 2
0 3
стандартный вывод
7
5
3
10
7
3Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 6 секунд
Ограничение по памяти: 512 мегабайт
Вам дан массив a1 = 1; a2 = 2,..., an = n и последовальность операций: переместить элементы с li по ri в начало массива. Например, для массива 2, 3, 6, 1, 5, 4 , после операции (2,4) новый по- рядок будет 3, 6, 1, 2, 5, 4. А после применения операции (3,4) порядок элементов в массиве будет 1, 2, 3, 6, 5, 4. Выведите порядок элементов в массиве после выполнения всех операций.
В первой строке входного файла указаны числа n и m ( 2 ⩽ n ⩽100 000, 1 ⩽ m ⩽100 000) — число элементов в массиве и число операций. Следующие m строк содержат операции в виде двух целых чисел: li и ri ( 1 ⩽ li ⩽ ri ⩽ n ).
Выведите n целых чисел — порядок элементов в массиве после применения всех операций.
стандартный ввод
6 3
2 4
3 5
2 2стандартный вывод
1 4 5 2 3 6Имя входного файла: log.in
Имя выходного файла: log.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Вы работаете со списком из строчных латинских букв. Изначально список пуст. Вы должны поддерживать следующие операции:
-
insert ⟨index⟩ ⟨number⟩ ⟨letter⟩ — добавить ⟨number⟩ букв ⟨letter⟩ перед буквой с индексом ⟨index⟩.
-
remove ⟨index⟩ ⟨number⟩ — удалить ⟨number⟩ букв, начиная с индекса ⟨index⟩.
-
query ⟨index 1 ⟩ ⟨index 2 ⟩ — вывести количество различных букв на отрезке с ⟨index 1 ⟩ до ⟨index 2 ⟩включительно.
Буквы нумеруются с 1.
В первой строке входного файла содержится единственное целое число n — количество операций ( 1 ⩽ n ⩽ 30 000). Следующие по n строк содержат описание операций. Описание операции начинается с типа операции: '+' для добавления, '-' для удаления и '?' для запроса. Дальше следует аргументы запроса, описанные в условиях выше. Все запросы корректны, элементы с такими индексами существуют, нет запросов на удаление несуществующих элементов. ⟨number⟩ добавления, удаления не превышает 10 000.
Для каждого запроса query выведите одно целое число — количество различных букв на отрезке ⟨index 1 ⟩, ⟨index 2 ⟩ включительно.
log.in
8
+ 1 4 w
+ 3 3 o
? 2 3
- 2 2
? 2 3
+ 2 2 t
? 1 6
- 1 6log.out
2
1
3Пояснение к примеру:
- wwww
- wwoooww
- w[wo]ooww: 2 различные буквы
- wooww
- w[oo]ww: 1 буква
- wttooww
- [wttoow]w: 3 различные буквы
- w
Имя входного файла: roads.in
Имя выходного файла: roads.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
В многострадальном Тридесятом государстве опять готовится дорожная реформа. Впрочем, на- до признать, дороги в этом государстве находятся в довольно плачевном состоянии. Так что реформа не повредит. Одна проблема — дорожникам не развернуться, поскольку в стране действует жесткий закон — из каждого города должно вести не более двух дорог. Все дороги в государстве двусторон- ние, то есть по ним разрешено движение в обоих направлениях (разумеется, разметка отсутствует). В результате реформы некоторые дороги будут строиться, а некоторые другие закрываться на бес- срочный ремонт. Петя работает диспетчером в службе грузоперевозок на дальние расстояния. В связи с предстоя- щими реформами, ему необходимо оперативно определять оптимальные маршруты между городами в условиях постоянно меняющейся дорожной ситуации. В силу большого количества пробок и со- трудников дорожной полиции в городах, критерием оптимальности маршрута считается количество промежуточных городов, которые необходимо проехать. Помогите Пете по заданной последовательности сообщений об изменении структуры дорог и за- просам об оптимальном способе проезда из одного города в другой, оперативно отвечать на запросы.
В первой строке входного файла заданы числа n — количество городов, m — количество дорог в начале реформы и q — количество сообщений об изменении дорожной структуры и запросов ( 1 ⩽ n, m ⩽ 100 000, q ⩽ 200 000). Следующие m строк содержат по два целых числа каждая — пары городов, соединенных дорогами перед реформой. Следующие q строк содержат по три элемента, разделенных пробелами. «+i j » означает строительство дороги от города i до города j, «-i j » означает закрытие дороги от города i до города j, «? i j » означает запрос об оптимальном пути между городами i и j. Гарантируется, что в начале и после каждого изменения никакие два города не соединены более чем одной дорогой, и из каждого города выходит не более двух дорог. Никакой город не соединяется дорогой сам с собой.
На каждый запрос вида «? i j » выведите одно число — минимальное количество промежуточ- ных городов на маршруте из города i в город j. Если проехать из i в j невозможно, выведите -1.
roads.in
5 4 6
1 2
2 3
1 3
4 5
? 1 2
? 1 5
- 2 3
? 2 3
+ 2 4
? 1 5roads.out
0
-1
1
2