Submission #1151220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151220		andrei_n	Addk (eJOI21_addk)	C++20	64 / 100	286 ms	8112 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;
int Left[400005],Right[400005];
int sum[400005];

void _update(int st, int dr, int node, int p, int x)
{
    if(st == dr)
    {
        Left[node] = Right[node] = x;
        sum[node] = x;
    }
    else
    {
        int mij = (st+dr)/2;
        if(p <= mij)
            _update(st, mij, node<<1, p, x);
        else
            _update(mij+1, dr, (node<<1)+1, p, x);

        sum[node] = sum[node<<1] + sum[(node<<1)+1];
        Left[node] = Left[node<<1] + Left[(node<<1)+1] + sum[(node<<1)+1] * (mij - st + 1);
        Right[node] = Right[node<<1] + Right[(node<<1)+1] + sum[node<<1] * (dr - mij);
    }
}

void _query(int st, int dr, int node, int a, int b, int what, int &res)
{
    if(st >= a && dr <= b)
    {
        if(what == 0) res += sum[node];
        else if(what == 1) res += Left[node] + sum[node] * (st - a);
        else               res += Right[node] + sum[node] * (b - dr);
    }
    else
    {
        int mij = (st+dr)/2;
        if(a <= mij)
            _query(st, mij, node<<1, a, b, what, res);
        if(b > mij)
            _query(mij+1, dr, (node<<1)+1, a, b, what, res);
    }
}

inline void update(int p, int x)
{
    _update(1, n, 1, p, x);
}

inline int query(int what, int a, int b)
{
    int res = 0;
    _query(1, n, 1, a, b, what, res);
    return res;
}

inline int query(int p)
{
    return query(0, p, p);
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int k,x; cin>>n>>k;
    for(int i=1; i<=n; ++i)
    {
        cin>>x;
        update(i, x);
    }
    int q; cin>>q;
    while(q--)
    {
        int t; cin>>t;
        if(t == 1)
        {
            vector<int> idx(k);
            for(auto &i:idx) cin>>i;
            int val = query(idx.front());
            for(int i=0; i<idx.size()-1; ++i)
                update(idx[i], query(idx[i+1]));
            update(idx.back(), val);
        }
        else
        {
            int l,r,m; cin>>l>>r>>m;
            int len = r-l+1;
            if(m > len/2) m = len+1-m;
            cout << query(1, l, l+m-1) + query(0, l+m, r-m) * m + query(2, r-m+1, r) << '\n';
        }
    }
    return 0;
}

/*
8 3
7 2 5 1 9 3 4 6
3
2 2 7 4
1 2 5 8
2 2 7 3
*/

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