Submission #1301714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301714		h1drogen	Addk (eJOI21_addk)	C++20	0 / 100	60 ms	6048 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define f first
#define s second  
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define imp cout<<-1<<"\n"
#define pb push_back
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define ls v<<1
#define rs v<<1|1
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ptree tree *
const int mod=1e9+7;
const int INF = 1e18;
const int sqr=317;
const int N=1e6;
int modi(int a,int b){
    return (a*b)%mod;
}
struct node{
    int tot;
    int acc;
    int dec;
};
struct segtree{
    vector<node>t;
    int n;
    void init(int sz){
        n=sz;
        t.resize(n*4);
    }
    void upd(int v,int tl,int tr,int pos,int val){
        if(tl==tr){
            t[v].tot+=val;
            t[v].acc=val*pos;
            t[v].dec=val*(n-pos);
        }
        else{
            int tm=(tl+tr)/2;
            if(pos<=tm){
                upd(ls,tl,tm,pos,val);
            }
            else
                upd(rs,tm+1,tr,pos,val);
            t[v].tot=t[ls].tot+t[rs].tot;
            t[v].acc=t[ls].acc+t[rs].acc;
            t[v].dec=t[ls].dec+t[rs].dec;
        }
    }
    int get1(int v,int tl,int tr,int l,int r){
        if(tl>r or l>tr) return 0LL;
        if(l<=tl and tr<=r){
            return t[v].acc;
        }
        int tm=(tl+tr)/2;
        return get1(ls,tl,tm,l,r)+get1(rs,tm+1,tr,l,r);
    }
    
    int get2(int v,int tl,int tr,int l,int r){
        if(tl>r or l>tr) return 0LL;
        if(l<=tl and tr<=r){
            return t[v].tot;
        }
        int tm=(tl+tr)/2;
        return get2(ls,tl,tm,l,r)+get2(rs,tm+1,tr,l,r);
    }
    int get3(int v,int tl,int tr,int l,int r){
        if(tl>r or l>tr) return 0LL;
        if(l<=tl and tr<=r){
            return t[v].dec;
        }
        int tm=(tl+tr)/2;
        return get3(ls,tl,tm,l,r)+get3(rs,tm+1,tr,l,r);
    }
};
void solve(){
    int n,m,k,a=1e18,b=0,c=0,d,e=0,f=0,q;
    cin>>n>>k;
    segtree t;
    t.init(n+1);
    vector<int>v(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        t.upd(1,1,n,i,v[i]);
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        int type,l,r,m;
        cin>>type;
        if(type==1){
            for(int j=0;j<k;j++)
                cin>>a;
        }
        else{
            cin>>l>>r>>m;
            int len=min((r-l+1)/2,m);
            int ans=0;
            // cout<<l<<" "<<l+len-1<<" "<<r-len+1<<" "<<r<<"\n";
            ans+=t.get1(1,1,n,l,l+len-1)-t.get2(1,1,n,l,l+len-1)*(l-1);
            // cout<<ans<<" ";
            ans+=t.get3(1,1,n,r-len+1,r)-t.get2(1,1,n,r-len+1,r)*(n-r);
            // cout<<ans<<" ";
            ans+=t.get2(1,1,n,l+len,r-len)*(r-l+1-len-len);
            cout<<ans<<"\n";
        }
    }
}
signed main(){
    fast;
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
}

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