Submission #593509

#	Time	Username	Problem	Language	Result	Execution time	Memory
593509		serkanrashid	Addk (eJOI21_addk)	C++14	0 / 100	159 ms	4660 KiB

Main

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

using namespace std;

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

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

void update(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return;
    if(l>=ql&&r<=qr)
    {
        pref[v]=val*r;
        suff[v]=val*(n-r+1);
        tree[v]=val;
        return;
    }
    int mid=(l+r)/2;
    update(v*2+0,l,mid+0);
    update(v*2+1,mid+1,r);
    pref[v]=pref[v*2]+pref[v*2+1];
    suff[v]=suff[v*2]+suff[v*2+1];
    tree[v]=tree[v*2]+tree[v*2+1];
}

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

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

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

void read()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    make_tree(1,1,n);
    cin >> q;
    int ch,l,r,m,idx,mid,obr;
    long long ans=0;
    for(int i=1;i<=q;i++)
    {
        cin >> ch;
        ans=0;
        if(ch==1)
        {
            for(int j=1;j<=k;j++)
            {
                cin >> b[j];
            }
            int pom_val=0;
            ql=b[1];
            qr=b[1];
            pom_val=query_tree(1,1,n);
            for(int j=1;j<k;j++)
            {
                ql=b[j+1];
                qr=b[j+1];
                val=query_tree(1,1,n);
                ql=b[j];
                qr=b[j];
                update(1,1,n);
            }
            val=pom_val;
            ql=b[k];
            qr=b[k];
            update(1,1,n);
        }
        else
        {
            cin >> l >> r >> m;
            m=min(m,r-l+2-m);
            idx=l+m-1;
            mid=(l+r)/2;
            idx=min(idx,mid);
            ql=l;
            qr=idx-1;
            ans+=query_pref(1,1,n);
            ans-=query_tree(1,1,n)*(l-1);
            obr=l+r-idx;
            ql=obr+1;
            qr=r;
            ans+=query_suff(1,1,n);
            ans-=query_tree(1,1,n)*(n-r);
            ql=idx;
            qr=obr;
            ans+=query_tree(1,1,n)*(idx-l+1);
            cout << ans << 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
6
2 3 8 4
2 5 6 2
2 6 8 1
2 1 8 4
2 1 8 6
2 3 7 2
*/

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