Wataru

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

Вы попробуйте только в одном месте путь передавать (или в конструкторе 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));

Вам надо перед циклами инициализировать переменные-аккамуляторы: Перед циклом по i нужно присвоить y = 1. Перед циклом по j нужно присвоить sum = 0.

Иначе у вас в sum накапливается сумма для всех разных i. А y вообще непонятно какое значение имеет до домножения.

Чтобы пропустить первый и последние элементы просто измените границы цикла:
for (int i = 1; i < 24; i++)

Если вы хотите эти элементы считать, если они больше единственного их соседа, то воспользуйтесь ленивым вычислением логических формул (при вычислении A || B, если A == true, то B вообще вычисляться не будет):

for (int i = 0; i < 25; i++)
  {
    if ((i +1 == n || ARR[i] > ARR[i + 1]) && 
         (i == 0 || ARR[i] > ARR[i - 1]))
      count++;
  }

По хорошему, вы должны использовать std::vector. А он умеет удалять все сам.

std::vector<int> a = {1, 2 ,3 ,4 ,5};
// Удалит элементы с l по r (l включительно, не удалит r).
// Если надо удалить r-ый элемент, то добавьте +1 во второй аргумент.
a.erase(a.begin()+l, a.begin()+r);

Если же вы хотите делать руками, то надо просто посмотреть, куда двигаются элементы. Те, что до l - не двигаются. Те, что от l до r - исчезают. Те, что после r сдвигаются влево на r-l+1 позиций.

for (i = l; i < n - 1 + l - r; ++i) {
  a[i] = a[i + r - l + 1];
}
// New length: n -1 + l - r;

y = c / d;

Вы делите целое число на целое. В языке С в этом случае происходит деление нацело. Чтобы в результате был float, вам надо один из операндов перобразовать во float/double. Можно или явно это написать, или просто прибавить 0.0:

y = (c + 0.0) / d;