Submission #1273208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273208		thesen	Addk (eJOI21_addk)	C++20	0 / 100	56 ms	3556 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vll vector<ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;

ll n, k;
void ad(vll &tree, ll ind, ll x){
    while(ind <= n){
        tree[ind] += x;
        ind += (ind&(-ind));
    }
}

ll query(vll &tree, ll l, ll r){
    if(l > r)return 0;
    ll res = 0;
    while(r > 0){
        res += tree[r];
        r -= (r&(-r));
    }l--;
    while(l > 0){
        res -= tree[l];
        l -= (l&(-l));
    }return res;
}

vll tree(1e5+1), ac(1e5+1), dc(1e5+1);
void add(ll ind, ll x){
    ad(tree, ind, x);
    ad(ac, ind, ind*x);
    ad(dc, ind, (n-ind+1)*x);
}

void solve(){
    cin >> n >> k;
    vll a(n+1); for(ll i = 1; i <= n; i++)cin >> a[i];

    for(ll i = 1; i <= n; i++){
        add(i, a[i]);
    }

    ll q; cin >> q;
    ll op, l, r, m, x;
    vll b(k), c(k);
    while(q--){
        cin >> op;
        if(op == 1){
            for(ll i = 0; i < k; i++) cin >> b[i];
            if(k==1)continue;
            for(ll i = 0; i < k-1; i++){
                c[i] = a[b[i+1]];
            }c[k-1] = a[b[0]];

            for(ll i = 0; i < k; i++){
                c[i] -= a[b[i]];
                a[b[i]] += c[i];
                add(b[i], c[i]);
            }
        }else{
            cin >> l >> r >> m;
            if(l == r){
                cout << a[l] << endl; continue;
            }
            x= (r-l+1); ll res = 0;
            if(x <= 2*m){
                ll mid = (l+r)/2;
                res += query(ac, l, mid);
                res -= (l-1) * query(tree, l, mid);
                res += query(dc, mid+1, r);
                res -= (n-r) * query(tree, mid+1, r);
            }else{
                res += query(ac, l, l+m-1);
                res -= (l-1) * query(tree, l, l+m-1);
                res += query(dc, r-m+1, r);
                res -= (n-r) * query(tree, r-m+1, r);
                res += m * query(tree, l+m, r-m);
            }cout << res << endl;
        }
    }
    
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll t=1; //cin >> t;
    for(int i = 1; i <= t; i++){
        solve();
    }
}

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