Антон Жучков, Наверно, что-то не так в вашем внешнем алгоритме. А что если самая длинная последовательность на конце? А последовательность на 1 короче - в самом начале?
Давайте вашу всю задачу, возможно тут надо не LCS вообще.
Если все же вам нужна первая LCS, то надо просто чуть-чуть модифицировать ваш алгоритм. Там, наверняка, где-то в цикле ищется максимальное число и вот там надо знаки правильно посавить (переписывать только если текущее значение строго больше пока найденого максимума).
В зависимости от реализации (порядок проверок, приоритет при совпадении длин) алгоритм действительно может искать самую последнюю или самую первую подпоследовательность.
Alexandroppolus, Так там и Q и M и N - сотни тысяч в задаче. Один запрос или одно число из запроса (потому что ограничение на сумму размеров всех запросов есть в конце условия) надо делать быстрее чем за линию.
zenz, Ну, так же, как у вас InputIterator'ы передаются - обозначте его, ну не знаю, Out. У него в коде функции можно будет делать присвоение и инкрементирование.
logan baby, Ну вам же сказали, делать во второй мапе ключами фамилии. Просто поменяйте местами параметры при запихивании во второй мап. И сделайте его std::multimap, если фамилии могут повторятся.
zenz, Нет, там точно что-то еще написано. Например, какой именно параметр он не может сматчить в шаблоне. Это сообщение компилятора должно вам однозначно намекнуть, что проблема в одном из ваших параметров в шаблонной функции. Конкретно в третьем. Посмотрите, какой тип имеет back_inserter и подумайте, каким образом оно может привестись к вашему параметру?
Откуда вы взяли про объединение? Или это хитрость из разряда "задавая вопрос в интернете, дайте на него неправильный ответ, тогда точно придут толпы разъяренных спорщиков и дадут правильный"?
Igor Borisov, Дело не в стиле. Дело в том, что там похоже меняли код случайным образом, пока на каком-то тесте не заработало. На других не работает, вот и спрашивают.
Alexandroppolus, можно и с О(sqrt(5000)) памяти. Сначала решетом найти для всех чисел до корня минимальный простой делитель. А потом искать gcd сливая списки простых. Если аккуратно подсчитать сколько там суммарно простых делителей среди всех чисел - будет линия.
Alexandroppolus, Я тоже сначала подумал про ответ за O(1). Даже какие-то формулы пытался выводить. Но там все не так просто, потому что надо, чтобы GCD(n,m) == 1, иначе тройки перебираются с повторами. Если и есть какая-то замкнутая формула, то там какой-нибудь ужас вроде дзетта-функции римана.
Давайте вашу всю задачу, возможно тут надо не LCS вообще.
Если все же вам нужна первая LCS, то надо просто чуть-чуть модифицировать ваш алгоритм. Там, наверняка, где-то в цикле ищется максимальное число и вот там надо знаки правильно посавить (переписывать только если текущее значение строго больше пока найденого максимума).