А есть способ уменьшит все элементы vector<uint64_t> v на константу,

помимо прохода циклом по v?

Есть, но это замена шила на мыло. Быстрее не будет

Можно ещё векторизовать, фьють ха

Можете хранить сумму этих констант отдельно, если размер вектора не меняется

Расскажите вашу задачу, может коллективно что-нибудь придумаем

да тут дело не в задаче, а в решении. Вот условие: https://contest.yandex.ru/contest/28412/problems/C/ Вот мое решение: #include<iostream> #include<algorithm> #include<vector> #include<map> #include<cmath> #include <numeric> using namespace std; int main() { int n, k; cin >> n >> k; vector<uint64_t> a(n); map<uint64_t, uint64_t> a_i_to_answer; // ввод for (auto& a_i : a) { cin >> a_i; a_i_to_answer[a_i]; } // медленное решение for (const auto& [key, value] : a_i_to_answer) { vector<uint64_t> copy_a = a; for (auto& a_i : copy_a) { int tmp = a_i - key; a_i = abs(tmp); } sort(copy_a.begin(), copy_a.end()); a_i_to_answer[key] = accumulate(copy_a.begin(), copy_a.begin() + k + 1, 0); } // вывод for (const auto& a_i : a) { cout << a_i_to_answer[a_i] << ' '; } return 0; } Вопрос исходный выше был мотивирован куском кода: for (auto& a_i : copy_a) { int tmp = a_i - key; a_i = abs(tmp); } так как являлось узким местом (key — как раз константа, которую я хотел бы вычетать за О(1) из всего вектора, как бы а что, а вдруг, это бы решило проблему, хотя и понимал, что такое маловероятно...). Но потом еще добавилось accumulate, и, крч, беда, не проходит по времени...

По ссылке надо регаться, задания не видно

Рассмотрим целочисленный массив a длины n. Назовём расстоянием от индекса i до множества индексов S величину dist(i,S)=∑j∈S∣∣ai−aj∣∣. Зафиксируем целое число k. Рассмотрим функцию f(i)=mindist(i,S), где минимум берётся по множествам S размера k, не содержащим индекс i. Определите значение f(i) для всех i от 1 до n. Формат ввода В первой строке заданы два целых числа n и k (2≤n≤300000, 1≤k<n), описанные в условии. Во второй строке содержится n целых чисел ai (1≤ai≤109) — элементы массива a. Формат вывода Выведите n целых чисел: значения f(i) для i=1,i=2,…,i=n. Пример 1 Ввод 4 2 1 2 3 4 Вывод3 2 2 3 Примечания Рассмотрим первый пример. При i=1 оптмиальное S — это {2,3}; dist(1,{2,3})=|1−2|+|1−3|=3. При i=2 оптмиальное S — это {1,3}; dist(2,{1,3})=|2−1|+|2−3|=2. При i=3 оптмиальное S — это {2,4}; dist(3,{2,4})=|3−2|+|3−4|=2. При i=4 оптмиальное S — это {2,3}; dist(4,{2,3})=|4−2|+|4−3|=3.

условие

При всём желании модифицировать все элементы некоторого контейнера за константу невозможно даже теоретически Ну ведь действительно, для этого необходимо по ним всем пройтись

Теоретически очень даже возможно - memcpy

Насколько я знаю, нигде это не написано

Только вот как тогда сделать такую магию, чтобы тот же memset задал значения вектору интов из 5 и 5 миллионов элементов за одно и то же время

Я исходил из того, что на практике memcpy гораздо эффективнее O(n), в таком случае теоретически что мешает на какой-то конкретной архитектуре быть ему O(1)?

Ох уж эта практика:)

Всё таки это не цикл с копированием каждого элемента

С чего бы...

Внутри нотаций О, Θ, Ω зашиты ещё и константы-множители memcpy нередко использует векторные инструкции, что уменьшает количество "копирований" Такими образом, вводится просто некоторый множитель 0 < k ≤ 1, но асимптотика всё равно останется линейной

А что это?

Это цикл с копированием каждого элемента

Хороший аргумент, соглашусь

Плохой. Не аргумент вообще

Почему нет?

помнится я в какой-то софтине видел вообще функцию, которая через AVX заполняла массив одинаковыми флоатами :)

Потому что Георгий просто тебе поддакивает, хотя суть от этого не меняется. Чтобы скопировать n элементов памяти надо О(n) операций. Всё. Почему это в документации вдруг не написано, мало что меняет

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

Ну это всё равно O(n)

стандарт никаких гарантий не накладывает на это, но законы физики таки накладывают :) а у них приоритет даже выше, чем у стандарта

Это уже философия на тему "что есть операция"?

не, ну если у тебя шина размером со всю оперативку...

Но время не будет расти линейно от числа элементов так-то

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

как это не будет

Асимптотически линейно Какого-нибудь логарифма там не добиться никогда Если при векторизации 5 и 6 элементов копируются за одно время, то это не значит, что зависимость нелинейная)

Да, но между n и скажем n/4 разница большая

Это уже не об асимптотике рассуждения тогда О(n/4) = O(n)

вообще в теории можно константное время, но это вряд ли существующее в природе железо надо. разве что какие-то ПЛИС, и то на очень маленьких физически ограниченных размерах.

Тогда O(2logn)=O(logn)? Где-то такая сложность мне встречалась, вроде даже в стандарте

Да

Да, это так

более того

Вот то есть чтобы прямо 5 элементов и миллиард друг от друга не отличались? Что-то мне подсказывает, что такое вряд ли осуществимо

если копировать между физически связанными один к одному ячейками памяти :)

Вот уж тут вообще никаких философий. Операция копирования...

Будет

А почему? Т.е, если я правильно помню, то нам для люблю операции копирования требуется взять переменную из одной ячейки и перенести в другую. Следовательно минимальная операция за 1 инструкцую асма. Следовательно для n элементов - n инструкций

Есть большие регистры, куда несколько переменных может уместиться

Стэк называется

Это не регистр

Rbp

https://en.m.wikipedia.org/wiki/Advanced_Vector_Extensions

Так ты про другое вообще говоришт

Есть векторные инструкции, с ними число инструкций/итераций будет меньше

Это если мы говорим про копирование куска памяти