Submission #583806

#	Time	Username	Problem	Language	Result	Execution time	Memory
583806		serkanrashid	Addk (eJOI21_addk)	C++14	0 / 100	51 ms	4204 KiB

Main

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const long long maxn=1e5+5;
long long n,k,q;
long long a[maxn],b[32];
long long dp[maxn];
long long pref[4*maxn],suff[4*maxn];
int ql,qr;

void make_tree1(int v, int l, int r)
{
    if(l==r)
    {
        pref[v]=a[r]*r;
        return;
    }
    int mid=(l+r)/2;
    make_tree1(v*2,l,mid);
    make_tree1(v*2+1,mid+1,r);
    pref[v]=pref[v*2]+pref[v*2+1];
}

void make_tree2(int v, int l, int r)
{
    if(l==r)
    {
        suff[v]=a[r]*(n-r+1);
        return;
    }
    int mid=(l+r)/2;
    make_tree2(v*2,l,mid);
    make_tree2(v*2+1,mid+1,r);
    suff[v]=suff[v*2]+suff[v*2+1];
}

long long query1(int v, int l, int r)
{
    if(r<ql||l>qr||l>r) return 0;
    if(l>=ql&&r<=qr) return pref[v];
    int mid=(l+r)/2;
    return query1(v*2,l,mid)+query1(v*2+1,mid+1,r);
}

long long query2(int v, int l, int r)
{
    if(r<ql||l>qr||l>r) return 0;
    if(l>=ql&&r<=qr) return suff[v];
    int mid=(l+r)/2;
    return query2(v*2,l,mid)+query2(v*2+1,mid+1,r);
}

void read()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        dp[i]=dp[i-1]+a[i];
    }
    cin >> q;
    make_tree1(1,1,n);
    make_tree2(1,1,n);
    int ty,l,r,m;
    for(int i=1;i<=q;i++)
    {
        cin >> ty;
        if(ty==1)
        {
            cin >> b[1];
        }
        else
        {
            cin >> l >> r >> m;
            long long sum=0;
            int ind1=l+m-2;
            ql=l;
            qr=ind1;
            if(ql<=qr)
            {
                sum+=query1(1,1,n);
                sum-=((l-1)*(dp[qr]-dp[ql-1]));
            }
            int ind2=r-m+2;
            ql=ind2;
            qr=r;
            if(ql<=qr)
            {
                sum+=query2(1,1,n);
                sum-=((l-1)*(dp[qr]-dp[ql-1]));
            }
            sum+=(m*(dp[ind2-1]-dp[ind1]));
            cout << sum << endl;
        }
    }
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	read();
return 0;
}
/*
8 1
7 2 5 1 9 3 4 6
3
2 2 7 4
1 1
2 2 7 3
*/

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