oj.uz

Submission #623359

# Submission time Handle Problem Language Result Execution time Memory
623359 2022-08-05T13:49:11 Z pakapu Addk (eJOI21_addk) C++14
100 / 100
 1378 ms 7668 KB 
    #pragma GCC optimize ("O3")
    #include <bits/stdc++.h>
     
    using namespace std;
     
    struct segtree {
     
        vector<long long> tree;
        int sz = 0;
     
        void init(int n) {
            sz = 1 << (32 - __builtin_clz(n - 1));
            tree.assign(sz * 2 - 1, 0);
        }
     
        void set(int pos, long long val, int x, int lx, int rx) {
            if(rx - lx == 1) {
                tree[x] = val;
                return;
            }
     
            int mid = (lx + rx) / 2;
     
            if(pos >= mid) {
                set(pos, val, x * 2 + 2, mid, rx);
            }
            else {
                set(pos, val, x * 2 + 1, lx, mid);
            }
     
            tree[x] = tree[x * 2 + 1] + tree[x * 2 + 2];
        }
     
        void set(int pos, long long val) {
            set(pos, val, 0, 0, sz);
        }
     
        long long get(int l, int r, int x, int lx, int rx) {
            if(rx <= l || lx >= r) {
                return 0;
            }
            if(lx >= l && rx <= r) {
                return tree[x];
            }
     
            int mid = (lx + rx) / 2;
            return get(l, r, x * 2 + 1, lx, mid) + get(l, r, x * 2 + 2, mid, rx);
        }
     
        long long get(int l, int r) {
            return get(l, r + 1, 0, 0, sz);
        }
     
        long long get_element(int x) {
            return tree[sz - 1 + x];
        }
     
        void set_element(int pos, long long val) {
            tree[sz - 1 + pos] = val;
        }
     
        void rebuild(int x, int lx, int rx) {
            if(rx - lx == 2) {
                tree[x] = tree[x * 2 + 1] + tree[x * 2 + 2];
                return;
            }
     
            int mid = (lx + rx) / 2;
            rebuild(x * 2 + 1, lx, mid);
            rebuild(x * 2 + 2, mid, rx);
            tree[x] = tree[x * 2 + 1] + tree[x * 2 + 2];
        }
        
        void rebuild() {
            rebuild(0, 0, sz);
        }
    };
     
    int main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     
        int n, k;
        cin >> n >> k;
     
        segtree sg;
        sg.init(n);
     
        for(int i = 0; i < n; i++) {
            long long tmp;
            cin >> tmp;
            sg.set_element(i, tmp);
        }
        sg.rebuild();
     
        int q;
        cin >> q;
        while(q--) {
            int x;
            cin >> x;
     
            if(x == 1) {
                vector<int> a(k);
                vector<long long> tmp(k);
     
                for(int i = 0; i < k; i++) {
                    cin >> a[i];
                    a[i]--;
                    //tmp[i] = sg.get(a[i], a[i]);
                    tmp[i] = sg.get_element(a[i]);
                }
                for(int i = 0; i < k; i++) {
                    sg.set(a[((i - 1) % k + k) % k], tmp[i]);
                }
            }
            else if(x == 2) {
                int l, r, m;
                cin >> l >> r >> m;
                l--;
                r--;
                long long s = 0;
                long long sprev = sg.get(l, r);
                for(int i = 0; i < min(r - l + 1 - m + 1, m) && r - l + 1 - 2 * i > 0; i++) {
                    s += sprev;
                    sprev = sprev - sg.get_element(l + i) - sg.get_element(r - i);
                }
                cout << s << '\n';
            }
        }
     
        return 0;
    }

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 456 KB Output is correct
5 Correct 8 ms 520 KB Output is correct
6 Correct 7 ms 588 KB Output is correct
7 Correct 9 ms 572 KB Output is correct
8 Correct 12 ms 700 KB Output is correct
9 Correct 21 ms 852 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1512 KB Output is correct
2 Correct 170 ms 1972 KB Output is correct
3 Correct 253 ms 2868 KB Output is correct
4 Correct 812 ms 5148 KB Output is correct
5 Correct 1378 ms 6308 KB Output is correct
6 Correct 1166 ms 6216 KB Output is correct
7 Correct 1027 ms 6148 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 3684 KB Output is correct
2 Correct 868 ms 5936 KB Output is correct
3 Correct 212 ms 7668 KB Output is correct
4 Correct 1205 ms 6612 KB Output is correct