Submission #1298209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298209		dang_hai_long	Addk (eJOI21_addk)	C++20	100 / 100	73 ms	4560 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<ll> bit;
    Fenwick(int n=0){ init(n); }
    void init(int n_){
        n = n_;
        bit.assign(n+1, 0);
    }
    void add(int idx, ll delta){
        for(; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }
    ll sumPrefix(int idx){
        ll res = 0;
        for(; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    ll rangeSum(int l, int r){
        if(l>r) return 0;
        return sumPrefix(r) - sumPrefix(l-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    if(!(cin >> N >> K)) return 0;
    vector<ll> A(N+1);
    for(int i=1;i<=N;i++) cin >> A[i];

    Fenwick bitA(N), bitJA(N);
    for(int i=1;i<=N;i++){
        bitA.add(i, A[i]);
        bitJA.add(i, A[i] * (ll)i);
    }

    int Q; cin >> Q;
    while(Q--){
        int type; cin >> type;
        if(type == 1){
            vector<int> idx(K);
            for(int i=0;i<K;i++) cin >> idx[i];
            vector<ll> old(K);
            for(int i=0;i<K;i++) old[i] = A[idx[i]];
            for(int i=0;i<K;i++){
                ll newv = old[(i+1)%K];
                int pos = idx[i];
                if(newv != A[pos]){
                    ll delta = newv - A[pos];
                    bitA.add(pos, delta);
                    bitJA.add(pos, delta * (ll)pos);
                    A[pos] = newv;
                }
            }
        } else if(type == 2){
            int L, R, m; cin >> L >> R >> m;
            int Send = R - m + 1;
            if(Send < L){
                cout << 0 << '\n';
                continue;
            }
            int p = Send;
            int q = min(R, L + m - 1);

            ll part1 = 0;
            if(L <= p){
                part1 = bitJA.rangeSum(L, p);
            }
            ll part2 = 0;
            if(p+1 <= R){
                ll sA = bitA.rangeSum(p+1, R);
                part2 = sA * (ll)Send;
            }
            ll Sum1 = part1 + part2;

            ll part3 = 0;
            if(L <= q){
                ll sA = bitA.rangeSum(L, q);
                part3 = sA * (ll)L;
            }
            ll part4 = 0;
            if(q+1 <= R){
                ll sum_jA = bitJA.rangeSum(q+1, R);
                ll sumA = bitA.rangeSum(q+1, R);
                part4 = sum_jA - (ll)(m-1) * sumA;
            }
            ll Sum2 = part3 + part4;

            ll totalA = bitA.rangeSum(L, R);
            ll answer = Sum1 - Sum2 + totalA;
            cout << answer << '\n';
        } else {
            
        }
    }
    return 0;
}

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