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, иначе тройки перебираются с повторами. Если и есть какая-то замкнутая формула, то там какой-нибудь ужас вроде дзетта-функции римана.
Даже не надо их генерировать. Достаточно перебрать n и m, найти k максимально возможное (поделив 5000 на c), прибавить к счетчику k. На максимум проверять надо 2km(m+n). У этого решения будет линейная сложность относительно ограничения на размер чисел.
