Submission #1326192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326192		hary	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	364 ms	10308 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;
vector<long long> c,rez;
set<long long> st;
long long n=0,q=0,k=0,x=0,s=0,t=0,u=0;
struct segmentree{
    vector<long long> tree;
    void init(){
        tree.assign(400001,0);
    }
    void build(long long x, long long l, long long r){
        if(r-l==0){
            tree[x]=c[l];
            return;
        }
        long long m=(l+r)/2;
        build(x*2+1,l,m);
        build(x*2+2,m+1,r);

        tree[x]=tree[2*x+1]+tree[2*x+2];
    }

    void update(long long x, long long l, long long r, long long i, long long v){
        if(r-l==0){
            tree[x]=v;
            //cout<<'!'<<tree[x]<<'\n';
            return;
        }
        long long m=(l+r)/2;
        if(i<=m) update(x*2+1,l,m,i,v);
        else update(x*2+2,m+1,r,i,v);

        tree[x]=tree[2*x+1]+tree[2*x+2];

    }

    long long sum(long long x, long long lx, long long rx, long long l, long long r){
        if(lx>r||rx<l)return 0;
        else if(lx>=l&&rx<=r){
                //cout<<tree[x]<<' ';
            return tree[x];
        }
        else{
            long long mx=(lx+rx)/2;
            long long lsum=sum(2*x+1,lx,mx,l,r);
            long long rsum=sum(2*x+2,mx+1,rx,l,r);

            return lsum+rsum;
        }
    }
};


int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


segmentree segtree;
cin>>n>>q>>k;
for(long long i=0;i<n;i++){
    cin>>x;
    c.push_back(x);
    if(x>0)st.insert(i);
}
segtree.init();
segtree.build(0,0,n-1);
for(long long i=0;i<q;i++){
    cin>>s>>t>>u;
    if(s==1){//now t and u == a and b
        t--;
        c[t]=u;
        if(u==0&&st.count(t)){
            st.erase(t);
        }else st.insert(t);
        segtree.update(0,0,n-1,t,u);
    }else if(s==2){
        if(k>1){
            auto lp=st.lower_bound(t-1);
            while(lp!=st.end()&&*lp<=u-1){
                long long pos=*lp;
                c[pos]/=k;
                segtree.update(0,0,n-1,pos,c[pos]);
                auto it=next(lp,1);
                if(c[pos]==0)st.erase(lp);
                lp=it;
            }
            //segtree.build(0,0,n);
        }

    }else{
        //cout<<'#';
        rez.push_back(segtree.sum(0,0,n-1,t-1,u-1));
        //cout<<'#' ;
    }
    //for(long long y:c){cout<<y<<' ';}
    //cout<<'\n';
}
for(long long y:rez){
    cout<<y<<'\n';
}
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75