oj.uz

Submission #641542

# Submission time Handle Problem Language Result Execution time Memory
641542 2022-09-17T03:00:50 Z Kanimet0 Addk (eJOI21_addk) C++17
100 / 100
 461 ms 12544 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)

const ll N = 1e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N], tree[N*4][3];
ll x, y, k;

void build(ll l, ll r, ll idx, ll cr){
    if (l == r){
        if (cr == 0) tree[idx][cr] = ar[l];
        else if (cr == 1) tree[idx][cr] = ar[l]*l;
        else tree[idx][cr] = ar[l]*(n-l+1);
        return;
    }
    ll md = (l+r)/2;
    build(l,md,idx*2,cr);
    build(md+1,r,idx*2+1,cr);
    tree[idx][cr] = tree[idx*2][cr]+tree[idx*2+1][cr];
}

ll que(ll l, ll r, ll idx, ll x, ll y, ll cr){
    if (l > r || l > y || r < x) return 0;
    if (x <= l && r <= y) return tree[idx][cr];
    ll md = (l+r)/2;
    return que(l,md,idx*2,x,y,cr)+que(md+1,r,idx*2+1,x,y,cr);
}

void upd(ll l, ll r, ll idx, ll pos, ll val, ll cr){
    if (l == r){
        if (cr == 0) tree[idx][cr] = val;
        else if (cr == 1) tree[idx][cr] = val*l;
        else tree[idx][cr] = val*(n-l+1);
        return;
    }
    ll md = (l+r)/2;
    if (pos <= md) upd(l,md,idx*2,pos,val,cr);
    else upd(md+1,r,idx*2+1,pos,val,cr);
    tree[idx][cr] = tree[idx*2][cr]+tree[idx*2+1][cr];
}

void input(){
}

void solve(){
    build(1,n,1,0);
    build(1,n,1,1);
    build(1,n,1,2);
    cin >> m;
    while(m--){
        ll a, b, c, d;
        cin >> a;
        if (a == 1){
            vector<ll> idx, val;
            ll lst;
            repp(i,1,k){
                cin >> b;
                idx.push_back(b);
                if (i != 1) val.push_back(ar[b]);
                else lst = ar[b];
            }
            val.push_back(lst);
            repz(i,0,k){
                upd (1,n,1,idx[i],val[i],0);
                upd (1,n,1,idx[i],val[i],1);
                upd (1,n,1,idx[i],val[i],2);
                ar[idx[i]] = val[i];
            }
            continue;
        }
        cin >> b >> c >> d;
        ll len = c-b+1;
        if (d > (len+1)/2) d = len-d+1;
        ll ten = que(1,n,1,b+d,c-d,0)*d;
        ll kir= que(1,n,1,b,b+d-1,1)-que(1,n,1,b,b+d-1,0)*(b-1);
        ll kan = que(1,n,1,c-d+1,c,2)-que(1,n,1,c-d+1,c,0)*(n-c);
        ll tot = kir+kan+ten;
        if (len%2 && d == (len+1)/2){
            tot -= que(1,n,1,b+d-1,b+d-1,0)*d;
        }
        cout << tot << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> ar[i];
    solve();
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 10 ms 596 KB Output is correct
6 Correct 13 ms 940 KB Output is correct
7 Correct 16 ms 924 KB Output is correct
8 Correct 19 ms 956 KB Output is correct
9 Correct 26 ms 1512 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2252 KB Output is correct
2 Correct 96 ms 3324 KB Output is correct
3 Correct 112 ms 5160 KB Output is correct
4 Correct 201 ms 9740 KB Output is correct
5 Correct 311 ms 11264 KB Output is correct
6 Correct 277 ms 10956 KB Output is correct
7 Correct 303 ms 10912 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 4188 KB Output is correct
2 Correct 302 ms 10564 KB Output is correct
3 Correct 461 ms 12544 KB Output is correct
4 Correct 341 ms 11580 KB Output is correct