Submission #602531

#	Time	Username	Problem	Language	Result	Execution time	Memory
602531		berr	Addk (eJOI21_addk)	C++17	92 / 100	158 ms	8676 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000005], st[1000005*4], b[1000005], c[1000005], n, k;

void build(int v, int l, int r)
{
    if(l==r) st[v]=a[l];
    else
    {
        build(v*2, l, (l+r)/2); 
        build(v*2+1, (l+r)/2+1, r);

        st[v]=st[v*2]+st[v*2+1];    
    }
}

int get(int v, int tl, int tr, int l, int r)
{
    if(l>tr||r<tl) return 0;
    else if(l>=tl&&r<=tr) return st[v];
    else
    {
        int mid=(l+r)/2;
        return get(v*2, tl, tr, l, mid)+get(v*2+1, tl, tr, mid+1, r);
    }
}

int dec(int l, int r)
{
    if(l>r) return 0;
    if(l==0) return b[r];
    else
    {

        return b[r]-b[l-1]-((l)*get(1, l, r, 0, n-1));
    }
}

int dec2(int l, int r)
{
    if(l>r) return 0;
    if(r==n-1) return c[l];
    else
    {
        return c[l]-c[r+1]-((n-r-1)*get(1, l, r, 0, n-1));
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin>>n>>k;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }

    build(1, 0, n-1);

    b[0]=a[0];
    for(int i=1; i<n; i++)
    {
        b[i]=(i+1)*a[i]+b[i-1];
    }
    c[n-1]=a[n-1];
    for(int i=n-2; i>=0; i--)
    {
        c[i]=(n-i)*a[i]+c[i+1];
    }
    int q; cin>>q;

    while(q--)
    {
        int type; cin>>type;
        if(type==1)
        {
            for(int i=0, x; i<k; i++) cin>>x;
        }
        else
        {
            int l, r, m; cin>>l>>r>>m;
            l--; r--;
            int ans=get(1, l, r, 0, n-1)*m;
            ans-=dec2(l, l+m-2);
            ans-=dec(r-m+2, r);
            cout<<ans<<"\n";
        }
    }
}

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