Wataru

Почитайте, что делает ostream_iterator.

Если итератору присвоить значение (it = 10;), то оно остается в памяти, при сдвигании итератора вперед (it++;) это значение записывается в выходной файл и следующее присвоение скормит итертору значение в следующей позиции. Этот итератор сделан, чтобы можно было писать в файл, как в C++ коллекцию (например, в вектор).

Важно, что у этого итератора оператор * ничего не делает, возвращает сам итератор. Оператор присвоения, кстати, тоже возвращает сам итератор.

Поэтому конструкция *(val%2 ? OddOut : EvenOut) вернет или итератор OddOut или EvenOut в зависимости от четности val. Далее, конструкция (... = val)++; запишет число val в один из выходных итераторов и сдвинет его на позицию вперед.

Весь код выше создает 2 output_iterator, для двух заданных файлов. Потом for_each через оператор() у класса скармливает ему входные числа из cin (тут работает istream_iterator, который позволяет читать из файлов, как из вектора). А класс, пользуясь конструкцией выше, записывает числа в один из двух файлов в зависимости от четности.

if (res1 = true)

Тут вы присваиваете переменной res1 значение true и потом смотрите на ее значение в условии.

Это вызвано тем, что оператор присврения возвращает значение переменной. Т.е. (res1 = true) == true. Если это вставить в if, то это то же самое что if(true).

Для сравнения нужно использовать "==".

Но, вообще говоря, if(res1 == true) - очень плохой код. Правильно писать if (res1).

Вам нужен std::map или std::unordered_map. Самому писать структуру данных не надо.

Первое будет деревом поиска, второе - хештаблицей.
Дерево поиска гарантированно будет работать стабильно быстро. Хеш таблица будет работать быстрее, но если вам не повезет, то может работать очень долго. Но предпочтительнее, на мой взгляд, таблица.

В качестве ключа используйте пару {Тип транспорта, номер маршрута}. В качестве значения - счетчик остановок.

Еще вам нужен еще один map из тип транспорта-> std::set или std::unordered_set номеров маршрутов.

Для построения структур один раз приходитесь по всем остановкам и увеличивайте счетчик в первой структуре. Добавляйте маршрут к транспорту во второй структуре.

Для поиска ответа пройдитесь циклом по всем элементам set из второго map - это все маршруты. Смотрите в первом map'е сколько остановок у этого маршрута и выбирайте максимум.

Вам уже дана формула n-го элемента.
В формуле, похоже, опечатка. Должно быть -1 в начале (если подставить n=0).
Но это не особо важно, все равно первые члены ряда считаются отдельно.

Соответственно, можно считать текущий элемент через предыдущий, как вы пытались:
a_k = a_(k-1)*(-x)*(2k+1)/(2k-1)/(2k-1)/(2k-2)

Только она не работает для k=1. Поэтому 2 первых члена ряда надо прибавить руками, а остальное в цикле i=2..n-1

Т.е. R вам не нужен, и в коде должно быть:

u = 1+3*x;
...
  u *= (-x)*(2i+1)/(2i-1)/(2i-1)/(2i-2);
  summa += u;

Да, еще стоит разобрать крайние случаи, если n =0, то надо отдельно вывести 1 (или -1, если мы исправляем опечатку).

У вас путь к файлу аж в трех местах написан!

Вы попробуйте только в одном месте путь передавать (или в конструкторе ofstream без вызоыва open() или используйте конструктор без параметров, но тогда оставьте open). И используйте string, раз уж его завели. И сделайте его const string заодно.

Пока вижу проблему, которая 100% приведет к тайм-лимиту. Вы при изменении приоритета ищите по всей очереди. Если вам дадут 500000 добавлений в очередь, а потом 500000 уменьшений случаного элемента, то ждать вы завершения программы будете очень долго.

Надо поддерживать массив позиций по по всем айдишникам. При любом перемещении пары элементов в массиве в очереди надо обновлять этот массив позиций.

При изменении приоретета уже не надо никакого find, потому что позиция уже будет доступна в массиве.

При добавлении нового элемента не надо вызывать build_heap. достаточно только shift_up от нового элемента. У вас в программе отдельно этой функции нет, но она фактически реализована в decrease_key. Только нужно, опять же, проходится не по всей очереди, а только по отцам. В цикле надо делать не i--, а i = (i+1)/2-1.

И ошибка как раз в decrease_key, У вас цикл по i, а внутри все время используется k.

В этой задаче все должно в long long помещаться. Никаких трюков не надо.

У вас ошибка вот тут:
long long div_up(int x, int y)

Типа параметров - int. Вы когда в эту функцию передаете long long сумму - происходит переполнение.

Просто измените типы на long long и должно пройти.

У вас какая-то странная схема в partition.

Представьте, что у вас массив из 2 элементов и первый - больше второго (a[0] = pivot > a[1]).

До цикла l = 0, h = 2, i = 0. Потом в первом while вы делаете i++. Потом сравниваете a[i] с pivot в первом while. a[1] < pivot по предположению, поэтому вы делаете i = 2. Все - вы уже вышли за границу массива.

Перепишите со стандартной схемой разбиения Хоара или Ломуто.

Или придется всякие условия i < j везде дописывать, но я не уверен.

Вроде все правильно. Какие ограничения? Может быть переполнение, ведь максимальный ответ n(n-1)/2. Для переполнения int достаточно 65536 чисел в массиве.

При копировании назад из временного массива b в массив a у вас индексация с ошибкой. Хоть b индексируется с 0, вы обращаетесь к элементам начиная с s.

unordered_map может работать за линию в худшем случае. Это если происходит много коллизий. Стандартная реализация еще и дико медленная, через связные списки работает и часто использует тривиальные хеши (буквально, значение int берется за значение хеша). Подобрать смертельный тест для такого хэша совсем не сложно. Введите вашей программе на вход координаты деревьев i*8192 - если я правильно понимаю, unordered_map будет работать ооочень долго.

Можно избавиться от таких тривиальных коллизий, если реализовать свою хеш функцию. А там можно хоть (x * 239017l) % (1<<31) возвращать. И то, лучше будет.

Еще, чтобы избавиться от постоянных рехешированний можно добавить вот это:

len.reserve(1048576);
len.max_load_factor(0.25);

Говорят, что если заранее зарезервировать место и указать load_factor поменьше, то unordered_map будет раз в 10 быстрее.

Плюс, константа у unorderd_map выше - ибо надо хеши считать и перехешировать всю таблицу, если чисел становится много. Может, оно бы было быстрее для миллиона чисел, а не 100000, как у вас там.

Вспомните алгоритм преобразования числа из 10-чной системы в t-ичную - надо делить на t с остатком, пока есть что делить. Остатки - цифры в t-ичной системе счисления (от младших к старшим).

Так, 323 в десятичной системе, если перевести в 16-ричную будет:
323 = 16*20+3. Остаток 3, результат 20.
20 = 16*1+4. Остаток 4, результат 1
1 = 16*0+1. Остаток 1. результат 0.

Отсюда получается, что искомое число в 16-ричной системе 143. Проверка 16*16*1+16*4+3 = 256+64+3=323

Итак, вам надо сделать то же самое, но не в 10-чиной системе, а в k-ичной (ведь переводим не из 10-чной а из k-ичной). Число записано в виде k-ичных цифр в массиве. Это, фактически, длинная арифметика с базой k.

Для этого надо реализовать деление числа в виде массива цифр на короткое с остатком.
Это делается со старших разрядов к младшим. Тупо делите каждую цифру с остатком отдельно. Остаток переносите в младший разряд. Последний остаток - это остаток от всего деления. Результаты делений - новые цифры.

Удобнее хранить цифры от младших к старшим в массиве. Т.е. элемент массива 0 - это единицы. Элемент 1 - это первая степень k. Еще стоит хранить номер последней ненулевой цифры. Смотрите реализацию по ссылке выше.

Вот пример из условия. Пусть k=666, t=10, число - {2, 179, 113} (в условии цифры от старших к младшим, но мы храним наоборот).

Делим на 10.

113/10 = 11 + остаток 3. Переносим 3 в младший разряд (умножив на 666), получаем 3*666+179=2177.
2177 / 10 = 217 + остаток 7. 7*666+2 = 4664.
4664 /10 = 466 + остаток 4. Дальше разрядов нет, значит 4 и есть остаток от деления {2, 179, 113} на 10. Результат деления - {466, 217, 11}

Последний остаток - 4 - это и есть младшая цифра в ответе (он в условии написан - 50241044). Надо продолжать делить результат пока он не окажется 0.

Повторим для {466, 217, 11}:
11/10 = 1 + остаток 1. 1*666+217 = 883
883/10 = 88 + остаток 3. 3*666+446 = 2444
2444/10 = 244 + остаток 4.
Опять, последний остаток - это остаток всего деления и следующая цифра в ответе (опять 4).
Результаты деления - {244, 88, 1}

И так далее, пока все число не станет 0 (все цифры в массиве 0).

Во-первых, для таких больших коэффициентов вы в long long не влезаете, если в лоб считать.

Можно проверить в 2 этапа. Подсчитать A=a*x+b, B=c*x+d. Потом проверить что A*x*x = -B. Но тут нужно заранее отсечь случаи, когда abs(A) > abs(B)/(x*x). Тогда переполнений не будет.

Во-вторых, как же сложно у вас разбор случаев идет. Я не могу разобраться, что там происходит. Там наверняка опечатка, но я даже читать не хочу. Перепишите, пожалуйста. Вам надо найти самый старший ненулевой коэффициент и перебирать его делители. Плюс добавить корень 0, если этот коэффициент не d. Это делается сильно проще так:

if (d != 0) {
  n = d;
} else {
  s.push_back(0);
  if (c != 0) {
    n = c;
  } else if (b != 0) {
   n = b;
  } else {
   n = a;
  }
}
if (n == 0) {cout << "-1"; return}

Судя по условию, надо считать среднее арифметическое, а вы ищите медиану.

Надо вместо сортировки тупо просуммировать все числа и поделить на их количество (округлите вниз).

Ну и, не забудьте в конце цикл гнать по всем элементам а не от середины.

У вас i - целое, а x - вещественное. При делении целого на целое идет деление нацело (с округлением вниз до целого). При делении целого на вещественное или вещественного на целое - результат вещественное.

Если лишние скобки поставить, то у вас сначала происходит деление нацело (2*i+1)/(2*i), а потом домножение на вещественное.
Без скобочек операции выполняются слева направо - a *(-1*x)*(2*i+1) даст вещественный результат, который точно поделится.

Если вы в скобочках приведете к вещественному, то у вас тоже все заработает: a = a *(-1*x)*((2*i+1.0)/(2*i));