Submission #1043906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043906		makanhulia	Addk (eJOI21_addk)	C++17	100 / 100	336 ms	12112 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,k;
int a[100001];
vector<pair<int,pair<int,int> > > st;

void build(int idx,int l,int r){
    if(l==r){
        st[idx].first=a[l];
        st[idx].second.first=l*a[l];
        st[idx].second.second=(n-l+1)*a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*idx,l,mid);
    build(2*idx+1,mid+1,r);
    st[idx].first=st[2*idx].first+st[2*idx+1].first;
    st[idx].second.first=st[2*idx].second.first+st[2*idx+1].second.first;
    st[idx].second.second=st[2*idx].second.second+st[2*idx+1].second.second;
}

void update(int idx,int l,int r,int pos,int val){
    if(l==r){
        st[idx].first=val;
        st[idx].second.first=l*val;
        st[idx].second.second=(n-l+1)*val;
        return ;
    }
    int mid=(l+r)/2;
    if(pos<=mid){
        update(2*idx,l,mid,pos,val);
    }
    else{
        update(2*idx+1,mid+1,r,pos,val);
    }
    st[idx].first=st[2*idx].first+st[2*idx+1].first;
    st[idx].second.first=st[2*idx].second.first+st[2*idx+1].second.first;
    st[idx].second.second=st[2*idx].second.second+st[2*idx+1].second.second;

}

pair<int,pair<int,int> > query(int idx,int l,int r,int posl,int posr){
    if(l>posr|| r<posl)return {0,{0,0}};
    if(l>=posl && r<=posr) return st[idx];
    int mid=(l+r)/2;
    pair<int,pair<int,int> >e=query(2*idx,l,mid,posl,posr);
    pair<int,pair<int,int> >b=query(2*idx+1,mid+1,r,posl,posr);
    return {e.first+b.first,{e.second.first+b.second.first,e.second.second+b.second.second}};
}

signed main(){
    cin>>n>>k;
    st=vector<pair<int,pair<int,int> > >(4*n+1);

    for(int q=1;q<=n;q++){
        cin>>a[q];
    }
    build(1,1,n);

    int u;
    cin>>u;
    while(u--){
        int type;
        cin>>type;
        if(type==1){
            int val[k+1];
            int idx[k+1];
            for(int q=1;q<=k;q++){
                cin>>idx[q];
                val[q]=query(1,1,n,idx[q],idx[q]).first;
            }
            for(int q=1;q<k;q++){
                update(1,1,n,idx[q],val[q+1]);
            }
            update(1,1,n,idx[k],val[1]);
        }
        else{
            int l,r,m;
            cin>>l>>r>>m;
            int seg=(r-l+1-m+1);
            m=min(seg,m);

            int posl=l+m-1;
            int posr=r-m+1;
            //cout<<posl<<" "<<posr<<endl;
            pair<int,pair<int,int> > awal=query(1,1,n,l,posl-1);
            pair<int,pair<int,int> > tngh=query(1,1,n,posl,posr);
            pair<int,pair<int,int> > akh=query(1,1,n,posr+1,r);

            int ans=awal.second.first-awal.first*(l-1);
            ans+=tngh.first * m;
            ans+=akh.second.second-akh.first*(n-r);
            cout<<ans<<endl;   
        }
    }
    

}

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