oj.uz

Submission #475534

# Submission time Handle Problem Language Result Execution time Memory
475534 2021-09-22T18:34:29 Z wildturtle Addk (eJOI21_addk) C++17
100 / 100
 425 ms 8672 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 9 ms 412 KB Output is correct
4 Correct 9 ms 332 KB Output is correct
5 Correct 13 ms 460 KB Output is correct
6 Correct 15 ms 460 KB Output is correct
7 Correct 19 ms 588 KB Output is correct
8 Correct 20 ms 640 KB Output is correct
9 Correct 28 ms 700 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1220 KB Output is correct
2 Correct 88 ms 1660 KB Output is correct
3 Correct 115 ms 2112 KB Output is correct
4 Correct 210 ms 3452 KB Output is correct
5 Correct 292 ms 4916 KB Output is correct
6 Correct 269 ms 4740 KB Output is correct
7 Correct 271 ms 4776 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 2444 KB Output is correct
2 Correct 300 ms 6320 KB Output is correct
3 Correct 425 ms 8672 KB Output is correct
4 Correct 311 ms 7620 KB Output is correct