Всем привет!
2 февраля мы начинаем сезон личных интернет-олимпиад — в 16:00 по московскому времени состоится первая личная интернет-олимпиада для школьников, которая также будет являться первым отборочным туром ИОИП. Вам предстоит помочь Аквамену и его друзьям справляться с множеством трудностей.
Продолжительность олимпиады — 5 часов. Не забудьте зарегистрироваться на цикл личных интернет-олимпиад в этом сезоне перед началом олимпиады, если вы не сделали этого раньше.
Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client.
Олимпиаду для вас подготовили подготовили Николай Будин (budalnik), Михаил Анопренко (manoprenko), Дмитрий Филиппов (DimaPhil) и Григорий Шовкопляс (GShark).
Для связи с жюри можно использовать адрес электронной почты [email protected]
Удачи!
Хотели провести олимпиаду, а получился контест на дерево отрезков
Вторая и третья решаются сетом, четвертая деревом фенвика :)
Третья с сетом на 100 заходит? Во второй лично для меня проще написать MergeSortTree.
Да заходит. Сначала помечаешь все позиции бомб из запросов как свободные и находишь для каждой клетки ближайшую занятую по всем направлениям (учитывая свободные клетки). Теперь идем с конца и поддерживаем сет для каждой строки и столбика. Когда запрос убрать бомбу мы наоборот добавляем её в сет строки и столбика. Если запрос узнать ответ то используем значения ближайших занятых и тех что хранятся в соответствующем сете строки или столбика.
В любом случае, при запросах только на удаление, во все сеты суммарно будет вставлено 2*10^6 элементов.
В третьей ещё можно просто поддерживать для каждого элемента следующий имеющийся элемент или -1 и сам двумерный массив. Когда приходит запрос на удаление просто помечать в массиве, что текущий элемент теперь равен 0. Когда запрос от данного элемента, смотрим на следующий, или на следующий от следующего и так далее и сжимаем путь как в СНМ. Получается видимо O(n log) как в СНМ с ооооочень маленькой константой, так как хороший тест против сжатия пути в СНМ сделать проблематично :).
Да, но мне пришлось это немного попихать
как задачу Б простым сетом решать О_о?
http://neerc.ifmo.ru/school/io/archive/20190202/tutorial-20190202-individual.pdf
Ой :)
Подумал что надо посчитать количество таких пар.
Итак, олимпиада закончилась — как решать?
Какую?
В принципе все
У кого-нибудь получилось решить С на 100 (не получить TLE), храня set имеющихся элементов для каждого столбца и ряда?
Ну 1e6 операций с сетом и не должно заходить