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

Автор Arseniy_Pavlov, 11 лет назад, По-русски

Здраствуйте.

Я уже обращался к сообществу по поводу того как решить эту задачу, мне подсказали что здесь нужна sqrt-декомпозиция, я попытался ее написать, но у меня ничего не вышло, и я забил

Недавно я вернулся к этой задаче, и понял что либо я понимаю под словами sqrt декомпозиция нечто другое, толи еще что, но я получил ТЛ9 Вот мой код http://pastebin.com/caX0v08G Скажите что я делаю не так? http://acm.timus.ru/problem.aspx?space=1&num=1613 — задача.

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

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

в "эта задача" надо писать "Эта" с заглавной буквой "Э", иначе мы не поймём, какая именно задача имеется в виду.

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

Эта задача решается проще.

Для каждого числа запомним, на каких позициях оно находится в исходном массиве. Далее для каждого запроса бинпоиском найдем первую позицию числа, которая больше левой границы в запросе. Если найденная позиция попадает в отрезок [l, r], выведем 1, иначе выведем 0. Сложность Q * logN.

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

когда присваивается flag=1, дальше что-то считать нет смысла — сразу делайте брейк и выводите ответ на запрос. Кроме того, не помешает заменить вектора на массивы и лонги на инты

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

    Спасибо, я сначала не верил что сработает брейкатся после того как нашел, вроде асимптотику не меняет.

    Но заслал и зашло.

    Спасибо!

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

Я использовал set и у меня был TL13. Изменил его на unordered_set и получил AC.

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

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