Submission #1309798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309798		empyr1n	Addk (eJOI21_addk)	C++20	100 / 100	80 ms	4564 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define el '\n'

using namespace std;

struct Fenwick {

    ll n;
    vector <ll> F;

    Fenwick (ll _n) {
        n = _n;
        F.assign(n + 1, 0);
    }

    void upd (ll i, ll val) {
        for (; i <= n; i += i & -i)
            F[i] += val;
    }

    ll get (ll i) {
        ll res = 0;
        for (; i > 0; i -= i & -i)
            res += F[i];
        return res;
    }

    ll sum (ll l, ll r) {
        if (l > r)
            return 0ll;
        return get(r) - get(l - 1);
    }

};

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, k; cin >> n >> k;

    Fenwick sum(n), sumi(n);
    vector <ll> a(n + 1);
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum.upd(i, a[i]);
        sumi.upd(i, a[i] * i);
    }

    ll q; cin >> q;
    while (q--) {
        int type; cin >> type;

        if (type == 1) {
            vector <ll> b(k), val(k);
            for (ll i = 0; i < k; i++) {
                cin >> b[i];
                val[i] = a[b[i]];
            }

            for (ll i = 0; i < k; i++) {
                ll r = val[(i + 1) % k] - a[b[i]];

                if (r) {
                    sum.upd(b[i], r);
                    sumi.upd(b[i], r * b[i]);
                    a[b[i]] = val[(i + 1) % k];
                }
            }
        } else {
            ll l, r, m; cin >> l >> r >> m;

            ll ans = 0;
            ans += sumi.sum(l, r - m + 1) + (r - m + 1) * sum.sum(r - m + 2, r) + sum.sum(l, r);
            ans -= l * sum.sum(l, l + m - 1) +
                   sumi.sum(l + m, r) - (m - 1) * sum.sum(l + m, r);

            cout << ans << el;
        }
    }
    return 0;
}

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