Информатика → Юниорская. Отбор → 2022 → 8 класс | BeyondOlympiads

Обсуждаем олимпиады
1
В этой теме обсуждаем задачи juniorselection олимпиады 2022 года
Это обсуждение публикации https://olympiads.bc-pf.org/informatics/juniorselection/2022/8
2

Задача A. Фонтан

Новый фонтан состоит из nn вертикально выровненных круглых резервуаров с водой, пронумерованных сверху вниз целыми числами, начиная с 11, как показано ниже:

`

[> Напечатайте или вставьте сюда код](https://i.imgur.com/TJON00r.png)

`

Каждый резервуар имеет свой диаметр, объем и кран, который может выпускать любое количество воды внутрь резервуара. Всякий раз, когда объем воды превышает вместимость резервуара, лишняя вода выливается из его стенок и стекает в ближайший снизу резервуар имеющий строго больший диаметр, или выливатеся на голову Мансура если такого резервуара нет. Вам необходимо ответить на qq запросов следующего вида: под каким номером водоема заканчивается сток, если из крана rr-го водоема выпустить v_ivi​ литров воды? Если в итоге вода выливается на голову Мансура, ответ должен быть 00.

Формат входного файла

Первая строка ввода содержит два целых числа — nn и qq. Следующие nn строк содержат по два целых числа d_idi​ и c_ici​ - диаметр и вместимость ii-го резервуара. Следующие qq строк содержат по два целых числа r_iri​ и v_ivi​.

Формат выходного файла

Выведите qq строк по одному целому числу в каждой — ответы на вопросы в том порядке, в котором они заданы.

Примеры

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

6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8

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

5
0
5
4
2
2 лайка
3

В чём нужна помощь?Чтобы получить ответ, нужно задать вопрос

4

помогите решить задачу

2 лайка
5

У вас есть мысли как можно попытаться решить эту задачу? Или даже не понимаете с чего начать?

6

второе

1 лайк
7

вопросы даются оффлайн, подумай что это тебе дает?
подсказка 1:

реши сначала для n <= 5000 и q <= 5000, посмотри что ты делаешь, может это можно как-то ускорить?

подсказка 2:

в решение за nq ты просто пробегаешься по массиву и ищешь следующий с большим диаметром и т.д, если ты отсортируешь запросы в убывающем порядке и будешь бежать с конца, можешь ли ты ускорить этот процесс?

подсказка 3:

давай будем хранить вектор для каждой такой пока сущесвутющей возврастающей последовательности, на нем можно бинпоиском искать первый момент когда суммарно хватит объема чтобы весь v покрыть(ну или найти что такого нету), подумай как быстро сумму на суффиксе вектора находить

подсказка 4:

давай будем хранить текующую сумму на возрастающей последовательности, и когда добавлять вектор добавлять и ее, так ты сможешь с помощью суффиксных сумм находить сумму на суффиксе за O(1)

6 лайков
8

Есть ли возможность проверить код на системе в кф? группа в кф

1 лайк
9

Нет, но это задача из Европейской Юниорской Олимпиады(EJOI) 2020 года. Ее можно дорешать на сайте eolymp.
Дорешка!

4 лайка