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

Timus 1613.
Автор tamirOK, 10 лет назад, По-русски

Здравствуйте! Помогите решить задачу.Я написал sqrt-декомпозицию, получил TLE на 13 тесте. Затем я написал сортировку и бинпоиск — получил TLE на 10 тесте.

Спасибо!

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

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

Лично я в ней написал sqrt-декомпозицию. Прошло такое решение: в каждой ячейке хранил хеш-таблицу/unordered_set из всех чисел, которые там есть. Изначально писал обычный set, тоже был TL13.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я сначала писал просто sqrt декомпозицию и получал тл 11, потому что устраивал бинпосик во всех блоках, которые попадают в этот интервал. А потом исправил так, что если ты в блоке уже нашел что, то остальные блоки проверять не надо И это прошло

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Обсуждение

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Можно с помощью дерева отрезков: http://e-maxx.ru/algo/segment_tree. Раздел "Поиск наименьшего числа, больше либо равного заданного, в указанном отрезке."

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Ребят, вы чего? Какая sqrt-Декомпозиция, какое дерево отрезков? Это же задача на сортировку и бин. поиск... http://ideone.com/t6zfxr

К автору: очень сложно помочь вслепую. Следовало хотя бы код приложить.

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

    Лол, и правда, а я тоже сдал sqrt-декомпозицию и бинпоиск внутри каждого блока

    → Ответить