АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1428. Список с пропусками

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

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

Описание: 856b4c3595473c88bfbaf608bcb5d6d9756d4bdb

Как видно из рисунка, структура состоит из нескольких упорядоченных связных списков, при этом каждый узел может находиться одновременно в нескольких списках.

В список первого уровня (самый нижний на рисунке) входят все узлы. В нашем примере это список Header → 3 → 6 → 8 → 9 → 11 → 13 → End.

В список второго уровня входит лишь какая-то часть узлов. На рисунке это список Header → 6 → 9 → 11 → End.

Аналогично, в список каждого следующего уровня входит подмножество узлов предыдущего списка. В нашем примере список третьего уровня это Header → 9 → 11 → End, список четвёртого уровня  Header → 11 → End.

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

Вставка новых элементов в список с пропусками осуществляется вероятностным алгоритмом при помощи генератора случайных чисел. При этом обычно используется следующее правило: примерно половина элементов должна принадлежать только списку первого уровня, четверть элементов спискам первого и второго уровня, одна восьмая спискам первого, второго и третьего уровня и так далее. Общее количество уровней, таким образом, пропорционально log2(N), где N количество элементов.

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

В данной задаче вам дан готовый список с пропусками, а также набор запросов на поиск элемента. Для каждого запроса определите, какое количество спусков на нижележащие уровни будет сделано во время поиска. Например, для поиска числа 11 потребуется сделать 0 спусков, для поиска числа 18 (которого нет в списке) 3 спуска.

Гарантируется, что список с пропусками сгенерирован вероятностным алгоритмом, и среднее время поиска одного элемента составляет O(log(N)).

 

Входные данные. Первая строка входных данных содержит целое число N (1 ≤ N ≤ 105) количество элементов структуры. Вторая строка содержит N пар разделенных пробелом целых чисел ai, bi  (−106ai ≤ 106, bi ≥ 1), где ai — значение в очередном узле, bi  — число списков, проходящих через этот узел (максимальный уровень узла). Все числа ai упорядочены по возрастанию.

В третьей строке находится целое число Q (1 ≤ Q ≤ 105) —  количество запросов поиска. В четвертой строке располагается Q разделенных пробелом целых чисел qi (−106qi ≤ 106) .

 

Выходные данные. Выведите Q целых чисел по одному в каждой строке — количество спусков, которое потребуется сделать при поиске каждого элемента.

 

Примеры

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

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

6

3 1 6 2 8 1 9 3 11 4 13 1

2

11 18

0

3

 

4

0 3 3 2 4 2 5 3

5

3 5 0 -5 -1

1

0

0

2

2

 

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XVIII межвузовская олимпиада 2015 /
1427. A - Календарь и первоклассники 1428. 1429. C - Крестики 1430. D - CodeFights 1431. E - Дробь
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Дополнительные задачи /
1427. 01 - Календарь и первоклассники 1428. 1429. 03 - Крестики 1430. 04 - CodeFights 1431. 05 - Дробь
 
время генерации 0.125 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.