Submission #1130616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130616		lopkus	Addk (eJOI21_addk)	C++20	92 / 100	143 ms	7544 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e5+50;

struct segtree{
    int t[4*N] = {0};
    int lazy[4*N] = {0};
    void propagate(int v,int tl,int tr){
        t[v]+=(tr-tl+1)*lazy[v];
        if(tl!=tr){
            lazy[v*2]+=lazy[v];
            lazy[v*2+1]+=lazy[v];
        }
        lazy[v]=0;
    }
    int query(int v,int tl,int tr,int l,int r){
        propagate(v,tl,tr);
        if(tl>=l&&tr<=r)return t[v];
        if(tl>r||tr<l)return 0;
        int tm=(tl+tr)/2;
        return (query(v*2,tl,tm,l,r)+query(v*2+1,tm+1,tr,l,r));
    }
    void update(int v,int tl,int tr,int l,int r,int value){
        propagate(v,tl,tr);
        if(tl>=l&&tr<=r){
            lazy[v]+=value;
            propagate(v,tl,tr);
            return;
        }
        if(tl>r||tr<l)return;
        int tm=(tl+tr)/2;
        update(v*2,tl,tm,l,r,value);
        update(v*2+1,tm+1,tr,l,r,value);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}seg;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> pref(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i];
        seg.update(1, 1, n, i, i,  pref[i]);
    }
    int q;
    cin >> q;
    while(q--) {
        int o;
        cin >> o;
        if(o == 1) {
            vector<int> b(k + 1);
            for(int i = 1; i <= k; i++) {
                cin >> b[i];
            }
            vector<int> c(k + 1);
            for(int i = 1; i <= k; i++) {
                int u = a[b[i]];
                c[i] = u;
                seg.update(1, 1, n, b[i], n, -u);
            }
            for(int i = 1; i < k; i++) {
                seg.update(1, 1, n, b[i], n, c[i + 1]);
            }
            seg.update(1, 1, n, b[k], n, c[1]);
        }
        else {
            int l, r, m;
            cin >> l >> r >> m;
            cout << seg.query(1, 1, n, l + m - 1, r) - seg.query(1, 1, n, l - 1, r - m) << "\n";
        }
    }
}

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