Submission #1295309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295309		uytfghjkl	Addk (eJOI21_addk)	C++20	0 / 100	29 ms	1980 KiB

Main

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

typedef long long ll;

class Fenwick {
private:
    int n;
    vector<ll> bit;

public:
    Fenwick(int n) : n(n), bit(n + 2, 0) {}

    void update(int idx, ll delta) {
        idx++;
        while (idx <= n) {
            bit[idx] += delta;
            idx += idx & -idx;
        }
    }

    ll query(int idx) {
        idx++;
        ll sum = 0;
        while (idx > 0) {
            sum += bit[idx];
            idx -= idx & -idx;
        }
        return sum;
    }

    ll range_query(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

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

    int N, K;
    cin >> N >> K;

    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    Fenwick bit1(N), bit2(N); // bit1: A[i], bit2: i*A[i]

    // Initialize Fenwick trees
    for (int i = 0; i < N; i++) {
        bit1.update(i, A[i]);
        bit2.update(i, (i + 1) * A[i]); // +1 because problem uses 1-based indexing
    }

    int Q;
    cin >> Q;

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            vector<int> indices(K);
            for (int i = 0; i < K; i++) {
                cin >> indices[i];
                indices[i]--; // to 0-based
            }
            // Circular left shift
            ll firstVal = A[indices[0]];
            for (int i = 0; i < K - 1; i++) {
                int idx = indices[i];
                int nextIdx = indices[i + 1];
                ll newVal = A[nextIdx];
                // Update Fenwick trees
                bit1.update(idx, newVal - A[idx]);
                bit2.update(idx, (idx + 1) * (newVal - A[idx]));
                A[idx] = newVal;
            }
            int lastIdx = indices[K - 1];
            bit1.update(lastIdx, firstVal - A[lastIdx]);
            bit2.update(lastIdx, (lastIdx + 1) * (firstVal - A[lastIdx]));
            A[lastIdx] = firstVal;
        } else {
            int l, r, m;
            cin >> l >> r >> m;
            l--; r--; // to 0-based
            int len = r - l + 1;
            int p = min(m, len - m + 1);

            // S1 = sum_{x=l}^{l+p-1} A[x] * (x-l+1)
            //    = sum_{x=l}^{l+p-1} (x+1)A[x] - l * sum_{x=l}^{l+p-1} A[x]
            ll sum1 = 0;
            if (p > 0) {
                ll sumXA = bit2.range_query(l, l + p - 1);
                ll sumA = bit1.range_query(l, l + p - 1);
                sum1 = sumXA - l * sumA;
            }

            // S2 = p * sum_{x=l+p}^{r-p} A[x]
            ll sum2 = 0;
            if (l + p <= r - p) {
                sum2 = p * bit1.range_query(l + p, r - p);
            }

            // S3 = sum_{x=r-p+1}^r A[x] * (r-x+1)
            //    = (r+1) * sum_{x=r-p+1}^r A[x] - sum_{x=r-p+1}^r x*A[x]
            ll sum3 = 0;
            if (p > 0) {
                ll sumA3 = bit1.range_query(r - p + 1, r);
                ll sumXA3 = bit2.range_query(r - p + 1, r);
                sum3 = (r + 1) * sumA3 - sumXA3;
            }

            cout << sum1 + sum2 + sum3 << "\n";
        }
    }

    return 0;
}

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