제출 #1273211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273211		thesen	Addk (eJOI21_addk)	C++20	0 / 100	90 ms	4464 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-1 <= 2*m){
                res += query(ac, l, l+(x-m)-1);
                res -= (l-1) * query(tree, l, l+(x-m)-1);
                res += query(dc, r-(x-m)+1, r);
                res -= (n-r) * query(tree, r-(x-m)+1, r);
                res += (x-m+1) * query(tree, l+(x-m), r-(x-m));
            }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;
            // ll res2 = 0;
            // for(ll i = l; i <= r-m+1; i++){
            //     res2 += query(tree, i, i+m-1);
            // }
            // if(res == res2)cout << "true";
            // else cout << "false";
            // cout << endl;
            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