Здраствуйте.
Я уже обращался к сообществу по поводу того как решить эту задачу, мне подсказали что здесь нужна sqrt-декомпозиция, я попытался ее написать, но у меня ничего не вышло, и я забил
Недавно я вернулся к этой задаче, и понял что либо я понимаю под словами sqrt декомпозиция нечто другое, толи еще что, но я получил ТЛ9 Вот мой код http://pastebin.com/caX0v08G Скажите что я делаю не так? http://acm.timus.ru/problem.aspx?space=1&num=1613 — задача.
в "эта задача" надо писать "Эта" с заглавной буквой "Э", иначе мы не поймём, какая именно задача имеется в виду.
Эта задача решается проще.
Для каждого числа запомним, на каких позициях оно находится в исходном массиве. Далее для каждого запроса бинпоиском найдем первую позицию числа, которая больше левой границы в запросе. Если найденная позиция попадает в отрезок [l, r], выведем 1, иначе выведем 0. Сложность Q * logN.
когда присваивается
flag=1, дальше что-то считать нет смысла — сразу делайте брейк и выводите ответ на запрос. Кроме того, не помешает заменить вектора на массивы и лонги на интыСпасибо, я сначала не верил что сработает брейкатся после того как нашел, вроде асимптотику не меняет.
Но заслал и зашло.
Спасибо!
Я использовал set и у меня был TL13. Изменил его на unordered_set и получил AC.
sqrt-декомпозицию удобнее писать более объектно-ориентированно, мне кажется. Код