Submission #1275155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275155		nonjapenzil	Sterilizing Spray (JOI15_sterilizing)	C++20	10 / 100	92 ms	9540 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nazi return 
#define cogito_ergo_sum ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll k;
struct hitler{
    ll n;
    vector<ll>rg;
    void init(ll n){
        rg.resize(4*n);
    }
    void build(ll v,ll l, ll r){
        if(l==r){
            rg[v]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(2*v,l,mid);
        build(2*v+1,mid+1,r);
    }
    ll nilber(ll v,ll l, ll r, ll x, ll y){
        if(l>y||x>r){
            return 0;
        }
        if(l>=x && r<=y ){
            return rg[v];
        }
        ll mid=(l+r)/2;
        return nilber( v*2,l,mid,x,y)+nilber(v*2+1,mid+1,r,x,y);
    }
    void update(ll v, ll l, ll r, ll bair , ll utg){
        if(bair<l||bair>r){
            return ;
        }
        if(l==r){
            rg[v]=utg;
            return;
        }
        ll mid=(l+r)/2;
        if(mid>=bair){
            update( 2*v, l,mid,bair,utg);
        }
        else{
            update(2*v+1,mid+1,r,bair,utg);
        }
        rg[v]=rg[v*2]+rg[2*v+1];
    }
    void div(ll v, ll l , ll r, ll bair){
        if(l==r){
            rg[v]/=k;
            return ;
        }
        ll mid=(l+r)/2;
        if(bair<=mid){
            div(2*v,l,mid,bair);
        }
        else{
            div(2*v+1,mid+1,r,bair);
        }
        rg[v]=rg[2*v]+rg[2*v+1];
    }

};
void PresentDay_PresentTime_HAHAHAHAHA(){
    ll n,q,k;
    cin>>n>>q>>k;
    hitler sg;
    sg.init(n);
    ll c[n+1];
    set<ll>s;
    for(ll i=1 ; i<=n ; i++ ){
        cin>>c[i];
        if(c[i]>0){
            s.insert(i);
        }
        sg.update(1,1,n,i,c[i]);
    }
    while(q--){
        ll t,x,y;
        cin>>t>>x>>y;
        if(t==1){
            sg.update(1,1,n,x,y);
            if(y>0){
                s.insert(x);
            }
        }
        if(t==2){
            if(k==1){
                continue;
            }
            ll cur=x;
            while(!s.empty()){
                auto pos=s.lower_bound(cur);
                if(pos==s.end()||*pos>y){
                    break;
                }
                ll sop=*pos;
                sg.div(1,1,n,sop);
                if(sg.nilber(1,1,n,sop,sop)==0){
                    s.erase(sop);
                }
                cur=*pos+1;
            }
            
        }
        if(t==3){
            cout<<sg.nilber(1,1,n,x,y)<<"\n";
        }
    }
    
}
int main(){
    cogito_ergo_sum;
    ll WelcomeToTheNHK=1;
    //cin>>WelcomeToTheNHK;
    while(WelcomeToTheNHK--){
        PresentDay_PresentTime_HAHAHAHAHA();
    }
}

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