Submission #1280694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280694		bahaktl	Addk (eJOI21_addk)	C++20	100 / 100	1378 ms	4740 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define int long long

const int N = 1e5+10;
const int inf = 1e18;

int t[N*4],a[N];

void update(int v,int tl,int tr,int pos) {
    if(tl==tr) {
        t[v]=a[tl];
        return;
    }
    int mid=(tl+tr)/2;
    if(pos>mid) update(v*2+1,mid+1,tr,pos);
    else update(v*2,tl,mid,pos);
    t[v]=t[v*2]+t[v*2+1];
}

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

signed main() {         
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int T;
    T=1;
    while(T--) {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            update(1,1,n,i);
        }
        int q;
        cin>>q;
        //cout<<k<<endl;
        while(q--) {
            int type;
            cin>>type;
            if(type==1) {
                int pos[k+1],val[k+1];
                for(int i=1;i<=k;i++) {
                    int x;
                    cin>>x;
                    pos[i]=x;
                    val[i]=a[x];
                }
                for(int i=1;i<=k;i++) {
                    if(i==k) a[pos[i]]=val[1];
                    else a[pos[i]]=val[i+1];
                    update(1,1,n,pos[i]);
                }
            }
            else {
                int l,r,m;
                cin>>l>>r>>m;
                int ans=get(1,1,n,l,r)*m;
                for(int i=m-1;i>0;i--,l++) {
                    ans-=a[l]*i;
                }
                for(int i=m-1;i>0;i--,r--) {
                    ans-=a[r]*i;
                }
                cout<<ans<<"\n";
            }
        }
    }
}   

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