Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Cart Sorting#29658

У Акакия есть колода, состоящая из n карт. На каждой карте написано ровно одно целое число от 1 до 100 000. Возможно, что на некоторых картах написаны одинаковые числа.

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

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

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

В первой строке следует целое положительное число n (1 ≤ n ≤ 100 000) — количество карт в колоде.

Во второй строке следует последовательность из n целых положительных чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 100 000), где a_i равно числу, написанному на i-й сверху карте из колоды.

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

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

Ввод	Вывод
4 6 3 1 2	7
1 1000	1
7 3 3 3 3 3 3 3	7

Примечание

В первом примере Акакий посмотрит сначала карту с числом 6, положит ее вниз колоды, затем карту с числом 3, также положит ее вниз колоды, и затем карту с числом 1. Он отложит карту с числом 1, так как на ней написан минимальное число из оставшихся в колоде. После этого карты в колоде будут лежать в порядке [2, 6, 3] сверху вниз. После этого Акакий посмотрит верхнюю карту с числом 2 и отложит её. После этого карты в колоде будут лежать в порядке [6, 3] сверху вниз. Затем Акакий посмотрит карту с числом 6, положит ее вниз колоды, а затем карту с числом 3, которую отложит. После этого в колоде останется одна карта с числом 6, которую Акакий посмотрит и отложит. Таким образом, Акакий посмотрит 7 карт.

(с) Курбатов Е., 2018

Декартово дерево

✓ 1✗ 31 100средняяВойти и решать

Двоичное дерево поиска 1#23571

Реализуйте сбалансированное двоичное дерево поиска.
ВНИМАНИЕ! Пользоваться vector и set из STL СТРОГО ЗАПРЕЩЕНО, однако рекомендуется стрессить ваше решение с ними для поиска багов.

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

В первой строке дано число n - количество операций с деревом. 1 <= n <= 100000.

Далее дается n строк – операции с деревом. В каждой строке находится одна из следующих операций:

1) insert x – добавить в дерево ключ x. Если ключ x уже в дереве, то ничего делать не нужно.

2) delete x – удалить из дерева ключ x. Если ключа x в дереве нет, то ничего делать не нужно.

3) exists x – если ключ х есть в дереве, то выведите “true”, иначе “false”.

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

Выведите последовательно результат выполнения всех операций exists. Каждый ответ нужно выводить в отдельной строке.

Пример:

Ввод	Вывод
6 insert 2 insert 5 insert 3 exists 3 exists 4 delete 5	true false

Двоичное дерево поиска Декартово дерево

✓ 18✗ 631 000средняяВойти и решать