Submission #1189209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189209		zadniprovska	Addk (eJOI21_addk)	C++20	0 / 100	33 ms	2632 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define el '\n'
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<long long, long long>
#define ppll pair< long long, pair<long long, long long> >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()

const ll DIM = 1e6+7;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxlog = 20;

ll a[DIM], p[17];

struct Fenwick {

    ll F[DIM] = {0};



    void update (ll pos, ll val) {

        pos++;
        for (int i=pos; i<DIM; i += i&-i) {
            F[i] += val;
        }

    }

    ll sum (ll pos) {

        pos++;
        ll ans = 0;
        for (int i=pos; i>0; i -= i&-i) {
            ans += F[i];
        }
        return ans;

    }

};

Fenwick F1, F2, F3;

void solve() {

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

    for (int i=1; i<=n; i++) {
        cin >> a[i];

        F1.update(i, a[i]);
        F2.update(i, i*a[i]);
        F3.update(i, (n-i+1)*a[i]);

    }


    ll nq;
    cin >> nq;
    for (int i=1; i<=nq; i++) {

        ll type;
        cin >> type;

        if (type == 1) {

            vector<ll> temp(k+1);
            for (int i = 1; i <= k; i++) {
                cin >> p[i];
                temp[i] = a[p[i]];
            }
            for (int i=1; i<k; i++) {
                F1.update(p[i], temp[i+1] - a[p[i]]);
                F2.update(p[i], p[i] * (temp[i+1] - a[p[i]]));
                F3.update(p[i], (n - p[i] + 1) * (temp[i+1] - a[p[i]]));
                a[p[i]] = temp[i+1];
            }

            F1.update(p[k], temp[1] - a[p[k]]);
            F2.update(p[k], p[k] * (temp[1] - a[p[k]]));
            F3.update(p[k], (n - p[k] + 1) * (temp[1] - a[p[k]]));
            a[p[k]] = temp[1];


        }

        else {
            ll L, R, m;
            cin >> L >> R >> m;

            ll len = R - L + 1;
            if (len >= 2*(m-1)) {

                ll res = F2.sum(L+m-2) - F2.sum(L-1) - (L-1)*(F1.sum(L+m-2) - F1.sum(L-1));

                res += F3.sum(R) - F3.sum(R-m+1) - (n-R)*(F1.sum(R) - F1.sum(R-m+1));

                res += m*(F1.sum(R-m+1) - F1.sum(L+m-2));

                cout << res << el;

            }
            else {
                ll m1 = len - m + 1;

                ll res = F2.sum(L+m1-2) - F2.sum(L-1) - (L-1)*(F1.sum(L+m1-2) - F1.sum(L-1));

                res += F3.sum(R) - F3.sum(R-m1+1) - (n-R)*(F1.sum(R) - F1.sum(R-m1+1));

                res += m*(F1.sum(R-m1+1) - F1.sum(L+m1-2));

                cout << res << el;
            }




        }



    }




}



signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    //freopen("nocross.in", "r", stdin);
    //freopen("nocross.out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--){
        solve();
    }
    return 0;

}
;

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