Submission #1100606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100606		irmuun	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	766 ms	12000 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

ll n,q,k;

struct segtree{
    vector<ll>d;
    void init(ll n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll v,ll l,ll r){
        if(l==r){
            d[v]=0;
            return;
        }
        ll m=(l+r)>>1;
        build(v*2,l,m);
        build(v*2+1,m+1,r);
        d[v]=d[v*2]+d[v*2+1];
    }
    ll query(ll v,ll l,ll r,ll L,ll R){
        if(L>R||l>R||L>r) return 0ll;
        if(L<=l&&r<=R){
            return d[v];
        }
        ll m=(l+r)>>1;
        return query(v*2,l,m,L,R)+query(v*2+1,m+1,r,L,R);
    }
    void update(ll v,ll l,ll r,ll pos,ll val){
        if(pos<l||r<pos) return;
        if(l==r){
            d[v]=val;
            return;
        }
        ll m=(l+r)>>1;
        update(v*2,l,m,pos,val);
        update(v*2+1,m+1,r,pos,val);
        d[v]=d[v*2]+d[v*2+1];
    }
    void update2(ll v,ll l,ll r,ll pos){
        if(pos<l||r<pos) return;
        if(l==r){
            d[v]/=k;
            return;
        }
        ll m=(l+r)>>1;
        update2(v*2,l,m,pos);
        update2(v*2+1,m+1,r,pos);
        d[v]=d[v*2]+d[v*2+1];
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q>>k;
    segtree sg;
    sg.init(n);
    ll c[n+5];
    set<ll>st;
    for(ll i=1;i<=n;i++){
        cin>>c[i];
        sg.update(1,1,n,i,c[i]);
        if(c[i]>0){
            st.insert(i);
        }
    }
    if(k==1){
        for(ll j=1;j<=q;j++){
            ll s,t,u;
            cin>>s>>t>>u;
            if(s==1){
                sg.update(1,1,n,t,u);
            }
            if(s==3){
                cout<<sg.query(1,1,n,t,u)<<"\n";
            }
        }
        return 0;
    }
    for(ll j=1;j<=q;j++){
        ll s,t,u;
        cin>>s>>t>>u;
        if(s==1){
            sg.update(1,1,n,t,u);
            if(u>0){
                st.insert(t);
            }
        }
        if(s==2){
            ll cur=t,i;
            while(!st.empty()){
                auto it=st.lower_bound(cur);
                if(it==st.end()||*it>u) break;
                ll i=*it;
                sg.update2(1,1,n,i);
                if(sg.query(1,1,n,i,i)==0){
                    st.erase(i);
                }
                cur=*it+1;
            }
        }
        if(s==3){
            cout<<sg.query(1,1,n,t,u)<<"\n";
        }
    }
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:99:22: warning: unused variable 'i' [-Wunused-variable]
   99 |             ll cur=t,i;
      |                      ^

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