Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2082. Конфетки
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 08/07/2014 | Лето 2014 - 07 (B) |
| 03/07/2017 | Лето 2017 - 5 (B) |
| 19/03/2024 | Дерево отрезков (начало) (проводит BOGAT) (A) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
У Кролика день рождения! Он пригласил в гости `n` гостей. Чтобы гостям не было
грустно и скучно, Кролик купил `n` коробок конфет. Кролик любит разнообразие,
поэтому конфеты были разные. В `i`-й коробке лежало `a_i` конфет.
В назначенный день с самого утра к Кролику начали приходить гости. Каждый гость
характеризуется своей наглостью `b_i`. Это означает, что, зайдя домой к Кролику
и увидев коробки конфет, он брал из каждой коробки, в которой не меньше, чем `b_i`,
конфет, по одной и съедал её. Например, у Винни-Пуха вполне могла была быть наглость
один. Это значит, что он бы съел по конфете из каждой коробки.
Вечером, когда гости разошлись, Кролику стало интересно, кто съел сколько конфет.
Помогите ему определить это.
В первой строке задано целое число `n` (`1\ ≤\ n\ ≤\ 100\ 000`) – количество коробок конфет. В следующей строке задано
`n` натуральных чисел `a_i` (`1≤\ a_i\ ≤\ 10^9`) – сколько конфет в каждой коробке.
Далее, в следующей строке задано число число `m` (`1≤\ m\ ≤\ 100\ 000`) – количество гостей. В четвёртой и
последней строке задано `m` чисел `b_i` (`1\ ≤\ b_i\ ≤\ 10^9`) – наглости гостей.
В выходной файл выведите `n` строк, `i`-ая из которых должна содержать
количество конфет съеденных `i`-ым гостем.
Пример ввода
3 3 1 1 2 1 1
Пример вывода
3 1
