Submission #595051

#	Time	Username	Problem	Language	Result	Execution time	Memory
595051		Urvuk3	Addk (eJOI21_addk)	C++17	0 / 100	8 ms	1408 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll INF=1e9,LINF=1e18,MOD=1e9+7; const ll MAXN=5001,MAXT=2001;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define pb push_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }

struct Node{
    ll s,pref,suf,d;
}seg[4*MAXN];

vector<int> a;

Node Merge(Node n1,Node n2){
    Node ret;
    if(n1.d==0) ret=n2;
    else if(n2.d==0) ret=n1;
    else{
        ret.s=n1.s+n2.s;
        ret.d=n1.d+n2.d;
        ret.pref=n1.pref+(n2.d*n1.s+n2.pref);
        ret.suf=n2.suf+(n1.d*n2.s+n1.suf);
    }
    return ret;
}

void Init(int node,int l,int r){
    if(l==r){
        seg[node].s=a[l];
        seg[node].pref=a[l];
        seg[node].suf=a[l];
        seg[node].d=1;
        return;
    }
    Init(2*node,l,mid); Init(2*node+1,mid+1,r);
    seg[node]=Merge(seg[2*node],seg[2*node+1]);
}

void Update(int node,int l,int r,int idx,int val){
    if(l==r){
        a[idx]=val;
        seg[node].s=val;
        seg[node].pref=val;
        seg[node].suf=val;
        seg[node].d=1;
        return;
    }
    if(idx<=mid) Update(2*node,l,mid,idx,val);
    else Update(2*node+1,mid+1,r,idx,val);
    seg[node]=Merge(seg[2*node],seg[2*node+1]);
}

Node Query(int node,int l,int r,int L,int R){
    Node ret; ret.s=ret.pref=ret.suf=ret.d=0;
    if(R<L) return ret;
    if(L<=l && r<=R){
        return seg[node];
    }
    if(L<=mid) ret=Merge(ret,Query(2*node,l,mid,L,R));
    if(R>mid) ret=Merge(ret,Query(2*node+1,mid+1,r,L,R));
    return ret;
}

void Solve(){
    int N,K; cin>>N>>K; a.resize(N+1);
    for(int i=1;i<=N;i++) cin>>a[i];
    Init(1,1,N);
    int Q; cin>>Q;
    while(Q--){
        int tip; cin>>tip;
        if(tip==2){
            int L,R,M;
            cin>>L>>R>>M;
            int cnt=(R-L+1)-(M-1);
            ll pref=Query(1,1,N,L,L+cnt-2).pref;
            ll suf=Query(1,1,N,R-cnt+2,R).suf;
            ll sum=Query(1,1,N,L,R).s;
            cout<<sum*cnt-pref-suf<<endl;
        }
        else{
            vector<int> idx1(K),idx2(K);
            for(int i=0;i<K;i++) cin>>idx1[i];
            idx2[K-1]=idx1[0];
            for(int i=K-2;i>=0;i--){
                idx2[i]=idx1[i+1];
            }
            vector<int> vals;
            for(int i=0;i<K;i++) vals.pb(a[idx2[i]]);
            for(int i=0;i<K;i++){
                Update(1,1,N,idx1[i],vals[i]);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        Solve();
    }
    return 0;
}

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