Submission #83300

#	Time	Username	Problem	Language	Result	Execution time	Memory
83300		Bodo171	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	331 ms	39640 KiB

sterilizing

#include <iostream>
#include <fstream>
#include <set>
using namespace std;
const int nmax=100005;
set<int> s;
set<int>::iterator it,it1;
long long aib[nmax];
int v[nmax];
int n,i,q,k,tip,val,poz,l,r;
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,long long val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
long long compute(int poz)
{
    long long ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=aib[idx];
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>q>>k;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        update(i,v[i]);
        s.insert(i);
    }
    s.insert(n+1);
    for(i=1;i<=q;i++)
    {
        cin>>tip;
        if(tip==1)
        {
            cin>>poz>>val;
            update(poz,-v[poz]);
            v[poz]=val;
            update(poz,v[poz]);
            s.insert(poz);
        }
        if(tip==2)
        {
            cin>>l>>r;
            if(k==1) continue;
            it=s.lower_bound(l);
            while((*it)<=r)
            {
                it1=it;it1++;
                poz=(*it);
                update(poz,-v[poz]);
                v[poz]/=k;
                update(poz,v[poz]);
                if(!v[poz])
                    s.erase(poz);
                it=it1;
            }
        }
        if(tip==3)
        {
            cin>>l>>r;
            cout<<compute(r)-compute(l-1)<<'\n';
        }
    }
    return 0;
}

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