제출 #1326189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326189		hary	Sterilizing Spray (JOI15_sterilizing)	C++20	0 / 100	130 ms	6036 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;
vector<int> c,rez;
set<int> st;
int n=0,q=0,k=0,x=0,s=0,t=0,u=0;
struct segmentree{
    vector<int> tree;
    void init(){
        tree.assign(200001,0);
    }
    void build(int x, int l, int r){
        if(r-l==0){
            tree[x]=c[l];
            return;
        }
        int 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(int x, int l, int r, int i, int v){
        if(r-l==0){
            tree[x]=v;
            //cout<<'!'<<tree[x]<<'\n';
            return;
        }
        int 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];

    }

    int sum(int x, int lx, int rx, int l, int r){
        if(lx>r||rx<l)return 0;
        else if(lx>=l&&rx<=r){
                //cout<<tree[x]<<' ';
            return tree[x];
        }
        else{
            int mx=(lx+rx)/2;
            int lsum=sum(2*x+1,lx,mx,l,r);
            int 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(int i=0;i<n;i++){
    cin>>x;
    c.push_back(x);
    st.insert(i);
}
segtree.init();
segtree.build(0,0,n);
for(int 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,t,u);
    }else if(s==2){
        if(k>1){
            auto lp=st.lower_bound(t-1);
            while(lp!=st.end()&&*lp<u){
                int pos=*lp;
                c[pos]/=k;
                segtree.update(0,0,n,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,t-1,u-1));
        //cout<<'#' ;
    }
    //for(int y:c){cout<<y<<' ';}
    //cout<<'\n';
}
for(int y:rez){
    cout<<y<<'\n';
}
    return 0;
}

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