Submission #1190470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190470		ezzzay	Addk (eJOI21_addk)	C++20	100 / 100	217 ms	6000 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=3e5+5;
int a[N];
int ps[N];
int PS[N],SF[N];
vector<int>ans;
int n,k;
void updateps(int idx, int val){
    while(idx<N){
        ps[idx]+=val;
        idx+= idx & -idx;
    }
}
int findps(int idx){
    if(idx==0)return 0;
    int s=0;
    while(idx>0){
        s+=ps[idx];
        idx-= idx & -idx;
    }
    return s;
}
void updatePS(int idx, int val){
    while(idx<N){
        PS[idx]+=val;
        idx+= idx & -idx;
    }
}
int findPS(int idx){
    if(idx==0)return 0;
    int s=0;
    while(idx>0){
        s+=PS[idx];
        idx-= idx & -idx;
    }
    return s;
}
void updateSF(int idx, int val){
    idx= n-idx+1;
    while(idx<N){
        SF[idx]+=val;
        idx+= idx & -idx;
    }
}
int findSF(int idx){
    idx= n-idx+1;
    if(idx==0)return 0;
    int s=0;
    while(idx>0){
        s+=SF[idx];
        idx-= idx & -idx;
    }
    return s;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        updateps(i, a[i]);
        updatePS(i,a[i]*i);
    }
    for(int i=n;i>=1;i--){
        updateSF(i,(n-i+1)*a[i]);
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            vector<int>v(k+1);
            for(int i=1;i<=k;i++){
                cin>>v[i];
                updateps(v[i],-a[v[i]]);
                updatePS(v[i],-a[v[i]]*v[i]);
                updateSF(v[i],-a[v[i]]*(n-v[i]+1));
            }
            int h=a[v[1]];
            for(int i=2;i<=k;i++){
                a[v[i-1]]=a[v[i]];
            }
            a[v[k]]=h;
            for(int i=1;i<=k;i++){
                updateps(v[i],a[v[i]]);
                updatePS(v[i],a[v[i]]*v[i]);
                updateSF(v[i],a[v[i]]*(n-v[i]+1));
            }
        }
        else{
            int l,r,m;
            cin>>l>>r>>m;
            int s=0;
            int k=min(m,r-l+1-m+1);
            int L=l+k-1;
            int R=r-k+1;
            s= (findps(R-1)-findps(L))*k;
            s+= (findPS(L)-findPS(l-1)) - (findps(L)-findps(l-1))*(l-1);
            s+= findSF(R)-findSF(r+1) - (findps(r)-findps(R-1))*(n-r);
            ans.pb(s);
        }
    }
    for(auto a:ans)cout<<a<<endl;
}

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