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

CF 12. Task D[SOLVED]
Автор stostap, 13 лет назад, По-английски
Can anyone explain me solution with interval tree? or any other solution?

P.S. I understand Russian

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

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

есть n точек в 3d x[i], y[i], z[i]

для простоты предположим что все координаты различны (по x , по y и по z)
сортируем по убыванию параметра x[i], затем по убыванию y[i]. делаем сжатие координат.

пусть a[i] = -inf для всех 1 <= i <= K (K = 10^6 например, после того как пожали координаты)

и на данном массиве мы умеем искать максимум на любом интервале (L, R)  за O(log(n)) , и обновлять значение в ячейке за O(log(n)).

рассматриваем точки в том порядке в котором посортировали

ищем максимум на интервале (y[i], K) если он больше чем z[i], то соответствующая дама потенциальная самоубийца.
обновляем a[y[i]] = max(a[y[i]], z[i]);


→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а именно суть масива a[] какова?
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

      Ссуть в песок. А массив нужен для определения того есть ли дама со всеми тремя параметрами больше чем у i-той,  меньшесть координаты x обеспечивается тем, что дамы обрабатываеются в порядке убывания её, по координате y это обеспечивается с помошью индекса в массиве, мы находим максимальную координату z которая уже была(т.е по X все ОК) в куске массива где y[j] > y[i], и сравниваем это с нашим z.массив А реализуется деревом отрезков.


      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        да, я поняв, пасиб
        я когда написал, потом сам поняв, что обрабативаем в порядке по убыванию.

        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как можно решать эту задачу, если точки имеют 4 координаты?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Из очевидного - написать двумерное дерево отрезков вместо одномерного. Правда тогда ответ на запрос будет за O(log2N).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если точек много, то двумерное дерево отрезков не поместится в памяти.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если точки заранее известны, то его можно сжать чтобы оно потребляло O(NlogN) памяти.
        → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Here is the explanation by kuniavski :
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ТЛ на 50 тесте
подскажите почему, pls!!!

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    по-моему, использование сета с мэпом для сжатия координат не оправдано. 5 * 10^5 на логаримф этого(~20). итого уже 10^7*k(константу сета/мэпа). К тому же там не только сет, а еще и мэп. а еще и делаешь ты это 3 раза, возвращаешь вектор и т.д. И все это только сжатие. а там ведь еще и решение самой задачи, которое при неплохой реализации требует 0,7-1 сек

    т.е. по-моему, нужно не злоупотреблять стл =)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ok, а как тогда умно можно сжать даные?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    AC, сжимать нужно только вторую координату 
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      поздравляю.

      я по-другому сжимать: отсортировать, и идя с начала переименовывать...
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Просьба составителям не делать в будущем такие ограничения по времени для такого объема входных данных. У меня на шарпе без плясок с бубном и ручной буфферизации на рандомном максимальном тесте только на чтение из консоли уходит почти три секунды. На java без BufferedReader'а, наверное, такие же проблемы вылезут. Возможно, что ещё на каких нибудь поддерживаемых тут языках родное консольное вычитывание лексем не очень быстрое.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На некоторых поддерживаемых языках не то что консольное считывание медленное, на них вообще половину задач сдать невозможно :)

    Например, я когда-то челленджил по времени линейное решение на php при N до 100000.
    → Ответить