Submission #775281

#	Time	Username	Problem	Language	Result	Execution time	Memory
775281		DuCanh2912	Addk (eJOI21_addk)	C++17	100 / 100	1487 ms	7116 KiB

Main

#include <bits/stdc++.h>

// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")

typedef unsigned short u16;
typedef short i16;
typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef float f32;
typedef double f64;
typedef long double f80;
typedef long double f128;

namespace std
{
    template <typename T, typename U>
    struct hash<pair<T, U>>
    {
        size_t operator()(const pair<T, U>& x) const { return hash<T>()(x.first) ^ hash<U>()(x.second); }
    };
}  // namespace std

struct custom_hash
{
    static u64 splitmix64(u64 x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    std::size_t operator()(u64 x) const
    {
        static const u64 rand_time = std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + rand_time);
    }
};

template <typename T>
using limits = std::numeric_limits<T>;

#ifdef LOCAL
#include <chrono>

#include "tools.hpp"
#define here(...)                                                                \
    std::cerr << __func__ << ':' << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; \
    _debug(__VA_ARGS__)
#else
#define here(...)
#endif

const u32 MAX_N = 100'000;
std::array<u64, MAX_N << 1> t;
u32 n;

void build()
{
    for (u32 i = n - 1; i > 0; --i)
    {
        t[i] = t[i << 1] + t[i << 1 | 1];
    }
}

void modify(u32 p, u64 val)
{
    for (t[p += n] = val; p > 1; p >>= 1)
    {
        t[p >> 1] = t[p] + t[p ^ 1];
    }
}

u64 query(u32 l, u32 r)
{
    u64 res{};
    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1)
        {
            res += t[l++];
        }
        if (r & 1)
        {
            res += t[--r];
        }
    }
    return res;
}

void solve()
{
    u32 k, q;
    std::cin >> n >> k;
    std::vector<u32> query_t1(k);
    for (u32 i = 0; i < n; ++i)
    {
        std::cin >> t[i + n];
    }
    build();
    std::cin >> q;
    while (q--)
    {
        u16 type;
        std::cin >> type;
        switch (type)
        {
            case 1:
            {
                for (auto& i : query_t1)
                {
                    std::cin >> i;
                    i--;
                }
                auto fi = t[n + query_t1[0]];
                for (u32 i = 0; i < k - 1; ++i)
                {
                    modify(query_t1[i], t[n + query_t1[i + 1]]);
                }
                modify(query_t1[k - 1], fi);
                break;
            }
            case 2:
            {
                u32 l, r, m;
                std::cin >> l >> r >> m;
                l--, r--;
                u32 cad_l = l;
                u64 res{}, sum = query(l, r + 1);
                for (u32 i = 0; i < m && l <= r && r >= cad_l + m - 1; ++i)
                {
                    res += sum;
                    sum -= t[n + l] + t[n + r];
                    l++, r--;
                }
                std::cout << res << '\n';
                break;
            }
            default:
                break;
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#ifdef LOCAL
    using std::chrono::duration_cast;
    using std::chrono::high_resolution_clock;
    using std::chrono::microseconds;
    auto st = high_resolution_clock::now();
    std::ifstream input("./in.txt");
    std::ofstream output("./log/bsol.txt");
    auto cin_buf = std::cin.rdbuf(input.rdbuf());
    auto cout_buf = std::cout.rdbuf(output.rdbuf());
#endif
    solve();
#ifdef LOCAL
    std::cin.rdbuf(cin_buf);
    std::cout.rdbuf(cout_buf);
    input.close();
    output.close();
    auto ed = high_resolution_clock::now();
    std::cerr << "Time elapsed: " << duration_cast<microseconds>(ed - st).count() << " microseconds\n";
#endif
    return 0;
}

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8