e-olymp 1225. Черный Ящик

by

0

Задача

Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную $i$. В начальный момент Черный Ящик пустой, переменная $i$ равна $0$. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить $i$ на $1$ и вывести $i$-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что $i$-ый минимальный элемент находится на $i$-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:

№ Транзакция $i$ Содержимое Черного Ящика после транзакции Ответ
1 ADD(3) 0 3
2 GET 1 3 3
3 ADD(1) 1 1, 3
4 GET 2 1, 3 3
5 ADD(-4) 2 -4, 1, 3
6 ADD(2) 2 -4, 1, 2, 3
7 ADD(8) 2 -4, 1, 2, 3, 8
8 ADD(-1000) 2 -1000, -4, 1, 2, 3, 8
9 GET 3 -1000, -4, 1, 2, 3, 8 1
10 GET 4 -1000, -4, 1, 2, 3, 8 2
11 ADD(2) 4 -1000, -4, 1, 2, 2, 3, 8

Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно $30000$ (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:

  1. $A_1, \ A_2, \ldots , \ A_m:$ последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие $2 000 000 000$, $m \leq 30000$. Для выше описанного примера $A = \left (3, 1, -4, 2, 8, -1000, 2 \right).$
  2. $u_1, \ u_2, \ldots , \ u_n:$ последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, … $n$-ой транзакции GET. Для выше описанного примера $u = \left (1, 2, 6, 6 \right ).$

Работа Черного Ящика предполагает, что числа в последовательности $u_1, \ u_2, \ldots , \ u_n$ отсортированы в неубывающем порядке, $n \leq m$, а для каждого $p \left (1 \leq p \leq n \right )$ имеет место неравенство $p \leq u(p) \leq m$. Это следует из того, что для $p$-го элемента последовательности $u$ мы выполняем GET транзакцию, которая выводит $p$-ый минимальный элемент из набора чисел $A_1, \ A_2, \ldots , \ A_{u_p}$.

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

Состоит из следующего набора чисел: $m, \ n, \ A_1, \ A_2, \ldots , \ A_m, \ u_1, \ u_2, \ldots , \ u_n.$ Все числа разделены пробелами и (или) символом перевода на новую строку.

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

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

Тесты

Входные данные Выходные данные
7 4
3 1 -4 2 8 -1000 2
1 2 6 6 		3
3
1
2
8 3
5 8 3 7 3 5 7 0
2 3 3		 5
5
8
10 4
6 3 7 3 8 4 7 4 6 15
4 6 8 9 		3
3
4
4
5 5
1 2 3 4 5
1 2 3 4 5 		1
2
3
4
5
11 5
4 6 8 9 5 3 6 8 10 12 13
6 7 8 9 10 		3
4
5
6
6

Код программы

Решение задачи

Пусть nums — множество всех элементов последовательности $A_n$. blackBox — мультимножество, представляющее собой описанный в задаче Черный Ящик на $i$-ом запросе. Изначально blackBox содержит «бесконечность» для избежания выхода за пределы. it — итератор, указывающий на $i$-ый минимальный элемент blackBox. Изначально данный итератор указывает на первый элемент множества. На $i$-ом запросе в blackBox копируются элементы массива nums от $u_{i-1}-1$-го до $u_{i}-1$-го (примем, что $u_0$ = 0). Тогда при добавлении в blackBox элемента, меньшего, чем тот, на который в данный момент указывает итератор it — $min_i$, $i$-ым минимальным элементом, становится элемент, предшествующий $min_i$. После выполнения ответа на $i$-ый запрос итератор должен указывать на $i+1$-ый минимальный элемент, то есть на элемент, следующий за $min_i$.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

Добавить комментарий