Блог пользователя manoprenko

Автор manoprenko, история, 6 лет назад, По-русски

Всем привет!

2 февраля мы начинаем сезон личных интернет-олимпиад — в 16:00 по московскому времени состоится первая личная интернет-олимпиада для школьников, которая также будет являться первым отборочным туром ИОИП. Вам предстоит помочь Аквамену и его друзьям справляться с множеством трудностей.

Продолжительность олимпиады — 5 часов. Не забудьте зарегистрироваться на цикл личных интернет-олимпиад в этом сезоне перед началом олимпиады, если вы не сделали этого раньше.

Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client.

Олимпиаду для вас подготовили подготовили Николай Будин (budalnik), Михаил Анопренко (manoprenko), Дмитрий Филиппов (DimaPhil) и Григорий Шовкопляс (GShark).

Для связи с жюри можно использовать адрес электронной почты iojury@gmail.com

Удачи!

  • Проголосовать: нравится
  • +61
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Хотели провести олимпиаду, а получился контест на дерево отрезков

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Вторая и третья решаются сетом, четвертая деревом фенвика :)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Третья с сетом на 100 заходит? Во второй лично для меня проще написать MergeSortTree.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Да заходит. Сначала помечаешь все позиции бомб из запросов как свободные и находишь для каждой клетки ближайшую занятую по всем направлениям (учитывая свободные клетки). Теперь идем с конца и поддерживаем сет для каждой строки и столбика. Когда запрос убрать бомбу мы наоборот добавляем её в сет строки и столбика. Если запрос узнать ответ то используем значения ближайших занятых и тех что хранятся в соответствующем сете строки или столбика.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          В любом случае, при запросах только на удаление, во все сеты суммарно будет вставлено 2*10^6 элементов.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +14 Проголосовать: не нравится

            В третьей ещё можно просто поддерживать для каждого элемента следующий имеющийся элемент или -1 и сам двумерный массив. Когда приходит запрос на удаление просто помечать в массиве, что текущий элемент теперь равен 0. Когда запрос от данного элемента, смотрим на следующий, или на следующий от следующего и так далее и сжимаем путь как в СНМ. Получается видимо O(n log) как в СНМ с ооооочень маленькой константой, так как хороший тест против сжатия пути в СНМ сделать проблематично :).

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

              Да, но мне пришлось это немного попихать

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      как задачу Б простым сетом решать О_о?

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Итак, олимпиада закончилась — как решать?

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

У кого-нибудь получилось решить С на 100 (не получить TLE), храня set имеющихся элементов для каждого столбца и ряда?