#include <algorithm>
#include <chrono>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <string>
#include <utility>
#include <numeric>
#include <vector>
template<typename T, typename K>
std::vector<K> sum_elements(const T& beg, const T& end, std::size_t k, K def)
{
if (k == 0) {
return std::vector<K>{};
}
return sum_elements(beg, end, k, def, [](auto &l, auto &r){ return r+l;});
}
template<typename T, typename K, class BinaryOp>
std::vector<K>
sum_elements(
const T& beg,
const T& end,
std::size_t k,
K def,
BinaryOp op)
{
std::vector<K> out;
out.reserve((std::distance(beg, end) - 1)/k + 1);
for (auto it = beg; it!=end; std::advance(it, std::min(static_cast<std::size_t>(std::distance(it, end)), k)))
{
out.push_back(std::accumulate(it, std::next(it, std::min(static_cast<std::size_t>(std::distance(it, end)), k)), def, op));
}
return out;
}
int main()
{
std::vector<int> vec;
auto size = 1000000;
vec.reserve(size);
for (int i=0; i < size; ++i)
vec.push_back(i);
auto beg = std::chrono::system_clock::now();
auto sum = 0;
for (int i=0; i < 100; i++)
sum += sum_elements(vec.begin(), vec.end(), 2, 0).size();
auto end = std::chrono::system_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end-beg).count() << std::endl;
std::cout << sum << std::endl;
return sum;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aXRlcmF0b3I+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dXRpbGl0eT4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDx2ZWN0b3I+CgoKdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUgSz4Kc3RkOjp2ZWN0b3I8Sz4gc3VtX2VsZW1lbnRzKGNvbnN0IFQmIGJlZywgY29uc3QgVCYgZW5kLCBzdGQ6OnNpemVfdCBrLCBLIGRlZikKewogaWYgKGsgPT0gMCkgewogICAgIHJldHVybiBzdGQ6OnZlY3RvcjxLPnt9OwogfQogcmV0dXJuIHN1bV9lbGVtZW50cyhiZWcsIGVuZCwgaywgZGVmLCBbXShhdXRvICZsLCBhdXRvICZyKXsgcmV0dXJuIHIrbDt9KTsKfQoKdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUgSywgY2xhc3MgQmluYXJ5T3A+CnN0ZDo6dmVjdG9yPEs+CiAgICBzdW1fZWxlbWVudHMoCiAgICAgICAgICAgIGNvbnN0IFQmIGJlZywKICAgICAgICAgICAgY29uc3QgVCYgZW5kLAogICAgICAgICAgICBzdGQ6OnNpemVfdCBrLAogICAgICAgICAgICBLIGRlZiwKICAgICAgICAgICAgQmluYXJ5T3Agb3ApCnsKICAgIHN0ZDo6dmVjdG9yPEs+IG91dDsKICAgIG91dC5yZXNlcnZlKChzdGQ6OmRpc3RhbmNlKGJlZywgZW5kKSAtIDEpL2sgKyAxKTsKICAgIGZvciAoYXV0byBpdCA9IGJlZzsgaXQhPWVuZDsgc3RkOjphZHZhbmNlKGl0LCBzdGQ6Om1pbihzdGF0aWNfY2FzdDxzdGQ6OnNpemVfdD4oc3RkOjpkaXN0YW5jZShpdCwgZW5kKSksIGspKSkKICAgIHsKICAgICAgICBvdXQucHVzaF9iYWNrKHN0ZDo6YWNjdW11bGF0ZShpdCwgc3RkOjpuZXh0KGl0LCBzdGQ6Om1pbihzdGF0aWNfY2FzdDxzdGQ6OnNpemVfdD4oc3RkOjpkaXN0YW5jZShpdCwgZW5kKSksIGspKSwgZGVmLCBvcCkpOwogICAgfQogICAgcmV0dXJuIG91dDsKfQoKaW50IG1haW4oKQp7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IHZlYzsKICAgIGF1dG8gc2l6ZSA9IDEwMDAwMDA7CiAgICB2ZWMucmVzZXJ2ZShzaXplKTsKICAgIGZvciAoaW50IGk9MDsgaSA8IHNpemU7ICsraSkKICAgICAgICB2ZWMucHVzaF9iYWNrKGkpOwogICAgYXV0byBiZWcgPSBzdGQ6OmNocm9ubzo6c3lzdGVtX2Nsb2NrOjpub3coKTsKICAgIGF1dG8gc3VtID0gMDsKICAgIGZvciAoaW50IGk9MDsgaSA8IDEwMDsgaSsrKQogICAgICAgIHN1bSArPSBzdW1fZWxlbWVudHModmVjLmJlZ2luKCksIHZlYy5lbmQoKSwgMiwgMCkuc2l6ZSgpOwogICAgYXV0byBlbmQgPSBzdGQ6OmNocm9ubzo6c3lzdGVtX2Nsb2NrOjpub3coKTsKICAgIHN0ZDo6Y291dCA8PCBzdGQ6OmNocm9ubzo6ZHVyYXRpb25fY2FzdDxzdGQ6OmNocm9ubzo6bWljcm9zZWNvbmRzPihlbmQtYmVnKS5jb3VudCgpIDw8IHN0ZDo6ZW5kbDsKICAgIHN0ZDo6Y291dCA8PCBzdW0gPDwgc3RkOjplbmRsOwoKICAgIHJldHVybiBzdW07Cn0K