Submission #475534

#	Time	Username	Problem	Language	Result	Execution time	Memory
475534		wildturtle	Addk (eJOI21_addk)	C++17	100 / 100	425 ms	8672 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a, b, c, d, i, e, f, g, n, m, k, l, r, x, t, ans, le, ri, lrev, rrev, lerev, rirev;
ll A[100005], B[100005], BITree[5][100005];
void updateBIT(ll x, ll idx, ll val) {
    idx++;
    while (idx < n + 3) {
        BITree[x][idx] += val;
        idx += idx & (-idx);
    }
}
ll getSum(ll x, ll idx) {
    idx++;
    ll sum = 0;
    while (idx > 0) {
        sum += BITree[x][idx];
        idx -= idx & (-idx);
    }
    return sum;
}
int main() {
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> A[i];
        updateBIT(1, i, A[i]);
        updateBIT(2, i, A[i]*i);
        updateBIT(3, n - i + 1, A[i] * (n - i + 1));
    }
    cin >> t;
    while (t--) {
        cin >> x;
        if (x == 1) {
            for (ll i = 1; i <= k; i++) {
                cin >> B[i];
            }
            B[0] = B[k];
            for (ll i = 1; i <= k; i++) {
                updateBIT(1, B[i], -A[B[i]]); updateBIT(1, B[i - 1], A[B[i]]);
                updateBIT(2, B[i], -A[B[i]]*B[i]); updateBIT(2, B[i - 1], A[B[i]]*B[i - 1]);
                updateBIT(3, n - B[i] + 1, -A[B[i]] * (n - B[i] + 1)); updateBIT(3, n - B[i - 1] + 1, A[B[i]] * (n - B[i - 1] + 1));
            }
            a = A[B[k]];
            for (ll i = k; i > 1; i--) {
                b = A[B[i - 1]];
                A[B[i - 1]] = a;
                a = b;
            }
            A[B[k]] = a;
            /*for (ll i = 1; i <= n; i++) {
                cout << A[i] << " ";
            }
            cout << endl;*/
        }
        else {
            cin >> l >> r >> m;
            lrev = n - l + 1; rrev = n - r + 1;
            ans = 0;
            if (l + m - 1 <= r - m + 1) {
                le = l + m - 1; ri = r - m + 1;
                lerev = n - le + 1; rirev = n - ri + 1;
                ans += m * (getSum(1, ri) - getSum(1, le - 1));
                //cout << ans << endl;
                ans += (getSum(2, le - 1) - getSum(2, l - 1)) - (l - 1) * (getSum(1, le - 1) - getSum(1, l - 1));
                //cout << ans << endl;
                //cout << r << " " << ri << endl;
                //cout << (getSum(3, rirev - 1) - getSum(3, rrev - 1)) << " " << (getSum(1, r) - getSum(1, ri )) << endl;
                ans += (getSum(3, rirev - 1) - getSum(3, rrev - 1)) - (rrev - 1) * (getSum(1, r) - getSum(1, ri ));
                //cout << ans << endl;
            } else {
                ri = l + m - 1; le = r - m + 1;
                rirev = n - ri + 1; lerev = n - le + 1;
                ans += (le - l + 1) * (getSum(1, ri) - getSum(1, le - 1));
                ans += (getSum(2, le - 1) - getSum(2, l - 1)) - (l - 1) * (getSum(1, le - 1) - getSum(1, l - 1));
                ans += (getSum(3, rirev - 1) - getSum(3, rrev - 1)) - (rrev - 1) * (getSum(1,  r) - getSum(1, ri));
            }
            cout << ans << endl;
        }
    }
}

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