제출 #1275159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275159		nonjapenzil	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	720 ms	9616 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);
        build(1,1,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);
        rg[v] = rg[2*v] + rg[2*v+1]; 
    }

    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(2*v,l,mid,x,y) + nilber(2*v+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;
        update(2*v,l,mid,bair,utg);
        update(2*v+1,mid+1,r,bair,utg);
        rg[v] = rg[2*v] + 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;
    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;
    while(WelcomeToTheNHK--) {
        PresentDay_PresentTime_HAHAHAHAHA();
    }
}

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