Submission #1295304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295304		uytfghjkl	Addk (eJOI21_addk)	C++20	0 / 100	30 ms	1916 KiB

Main

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

struct Fenwick {
    int n;
    vector<long long> bit;

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

    void update(int i, long long delta) {
        for (; i <= n; i += i & -i)
            bit[i] += delta;
    }

    long long query(int i) {
        long long s = 0;
        for (; i > 0; i -= i & -i)
            s += bit[i];
        return s;
    }

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

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

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

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++)
        cin >> A[i];

    Fenwick FT1(N), FT2(N);

    for (int i = 1; i <= N; i++) {
        FT1.update(i, A[i]);
        FT2.update(i, A[i] * 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];

            long long first = A[idx[0]];

            for (int i = 0; i < K - 1; i++) {
                long long oldv = A[idx[i]];
                long long newv = A[idx[i + 1]];

                A[idx[i]] = newv;

                FT1.update(idx[i], newv - oldv);
                FT2.update(idx[i], (newv - oldv) * idx[i]);
            }

            long long oldv = A[idx[K - 1]];
            long long newv = first;

            A[idx[K - 1]] = newv;

            FT1.update(idx[K - 1], newv - oldv);
            FT2.update(idx[K - 1], (newv - oldv) * idx[K - 1]);
        }

        else {
            int l, r, m;
            cin >> l >> r >> m;

            int L1 = l;
            int R1 = l + m - 1;

            int L2 = l + m;
            int R2 = r - m + 1;

            int L3 = r - m + 2;
            int R3 = r;

            long long ans = 0;

            if (L1 <= R1) {
                long long sumA = FT1.range(L1, R1);
                long long sumAi = FT2.range(L1, R1);
                ans += sumAi - 1LL * (L1 - 1) * sumA;
            }

            if (L2 <= R2) {
                long long sumA = FT1.range(L2, R2);
                ans += 1LL * m * sumA;
            }

            if (L3 <= R3) {
                long long sumA = FT1.range(L3, R3);
                long long sumAi = FT2.range(L3, R3);
                ans += 1LL * (r + 1) * sumA - sumAi;
            }

            cout << ans << "\n";
        }
    }

    return 0;
}

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