Submission #388641

#	Time	Username	Problem	Language	Result	Execution time	Memory
388641		MasterTaster	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	432 ms	9560 KiB

sterilizing

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 100010

using namespace std;

int n, q, k;
ll a[MAXN], bit[MAXN];
set<int> koji;

void upd(int x, ll v)
{
    while (x<MAXN)
    {
        bit[x]+=v;
        x+=x&(-x);
    }
}
ll sum(int x)
{
    ll ret=0;
    while (x)
    {
        ret+=bit[x];
        x-=x&(-x);
    }
    return ret;
}

int main()
{
    cin>>n>>q>>k;

    for (int i=1; i<=n; i++) { cin>>a[i]; upd(i, a[i]); if (a[i]) koji.insert(i); }

    while (q--)
    {
        int t; cin>>t;
        if (t==1)
        {
            ll x, v; cin>>x>>v;
            upd(x, v-a[x]);
            if (v) koji.insert(x);
            a[x]=v;
        }
        else if (t==2)
        {
            int l, r; cin>>l>>r;
            if (k==1) continue;
            for (auto it=koji.lower_bound(l); it!=koji.end() && (*it)<=r; it++)
            {
                int x=*it;
                //cout<<x<<" ala "<<a[x]<<endl;
                if (a[x]==0) continue;

                upd(x, a[x]/k-a[x]);
                a[x]/=k;
            }
            for (auto it=koji.lower_bound(l); it!=koji.end() && (*it)<=r; it++)
            {
                int x=*it;
                if (a[x]==0) koji.erase(it);
            }
        }
        else
        {
            int l, r; cin>>l>>r;
            cout<<sum(r)-sum(l-1)<<endl;
        }

        /*for (int i=1; i<=n; i++) cout<<a[i]<<" ";
        cout<<endl;
        for (auto it:koji) cout<<(it)<<" ";
        cout<<endl;*/
    }
}

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