oj.uz

Submission #775312

# Submission time Handle Problem Language Result Execution time Memory
775312 2023-07-06T09:34:56 Z CESxRhino Addk (eJOI21_addk) C++17
100 / 100
 265 ms 10396 KB 
#include <iostream>
#include <deque>
using namespace std;
long long int a[100005], d[1000005], lazy[1000005];
void push(int v, int tl, int tr) {
    int mid = (tl + tr) / 2;
    d[v * 2] += lazy[v] * (mid - tl + 1);
    d[v * 2 + 1] += lazy[v] * (tr - mid);
    lazy[v * 2] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, long long int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        d[v] += x * (r - l + 1);
        lazy[v] += x;
        return;
    }
    push(v, tl, tr);
    int mid = (tl + tr) / 2;
    update(v * 2, tl, mid, l, min(r, mid), x);
    update(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
    d[v] = d[v * 2] + d[v * 2 + 1];
}
long long int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return d[v];
    }
    push(v, tl, tr);
    int mid = (tl + tr) / 2;
    return sum(v * 2, tl, mid, l, min(r, mid)) + sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n, k, q, c = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c += a[i];
        update(1, 0, n, i, n, a[i]);
    }
    cin >> q;
    for (int jj = 0; jj < q; jj++) {
        long long int w, l, r, x;
        cin >> w;
        if (w == 2) {
            cin >> l >> r >> x;
            int h = (l + x - 1), k = r - x;
            cout << sum(1, 0, n, h, r) - sum(1, 0, n, l - 1, k) << '\n';
        }
        else {
            deque<int> v, d;
            for (int i = 0; i < k; i++) {
                int x;
                cin >> x;
                v.push_back(x);
                d.push_back(x);
            }
            d.push_back(d[0]);
            d.pop_front();
            for (int i = 0; i < k; i++) {
                update(1, 0, n, v[i], n, a[d[i]] - a[v[i]]);
            }
            int h = a[v[0]];
            for (int i = 0; i < k - 1; i++) {
                a[v[i]] = a[d[i]];
            }
            a[v[k - 1]] = h;
            //for (int i = 1; i <= n; i++) cout << a[i] << " ";
            //cout << endl;
        }
    }
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 6 ms 852 KB Output is correct
8 Correct 8 ms 852 KB Output is correct
9 Correct 10 ms 1272 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1748 KB Output is correct
2 Correct 33 ms 2668 KB Output is correct
3 Correct 47 ms 4152 KB Output is correct
4 Correct 93 ms 7684 KB Output is correct
5 Correct 124 ms 9164 KB Output is correct
6 Correct 117 ms 8908 KB Output is correct
7 Correct 116 ms 8920 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 3280 KB Output is correct
2 Correct 121 ms 8524 KB Output is correct
3 Correct 265 ms 10396 KB Output is correct
4 Correct 142 ms 9376 KB Output is correct