Submission #565999

#	Time	Username	Problem	Language	Result	Execution time	Memory
565999		groshi	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	224 ms	2404 KiB

sterilizing

    #include<iostream>
     
    using namespace std;
    int k;
    long long drzewo[3000000];
    int pot=1;
    long long zap(int x,int l,int r,int a,int b)
    {
        if(r<a || l>b)
            return 0;
        if(l>=a && r<=b)
            return drzewo[x];
        int mid=(l+r)/2;
        return zap(x*2,l,mid,a,b)+zap(x*2+1,mid+1,r,a,b);
    }
    void add(int x,int l,int r,int a,int b)
    {
        if(r<a || l>a)
            return;
        if(l==r)
        {
            drzewo[x]=b;
            return;
        }
        int mid=(l+r)/2;
        add(x*2,l,mid,a,b);
        add(x*2+1,mid+1,r,a,b);
        drzewo[x]=drzewo[x*2]+drzewo[x*2+1];
    }
    void spray(int x,int l,int r,int a,int b)
    {
        if(l>b || r<a)
            return;
        if(drzewo[x]==0)
            return;
        if(l==r)
        {
            drzewo[x]/=k;
            return;
        }
        int mid=(l+r)/2;
        spray(x*2,l,mid,a,b);
        spray(x*2+1,mid+1,r,a,b);
        drzewo[x]=drzewo[x*2]+drzewo[x*2+1];
    }
    int main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int n,q,x;
        cin>>n>>q>>k;
        while(pot<=n)
            pot*=2;
        pot--;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            add(1,pot+1,pot*2+1,i+pot,x);
        }
        while(q--)
        {
            int x,a,b;
            cin>>x>>a>>b;
            if(x==1)
                add(1,pot+1,pot*2+1,a+pot,b);
            if(x==2)
            {
                if(k==1)
                    continue;
                spray(1,pot+1,pot*2+1,a+pot,b+pot);
            }
            if(x==3)
                cout<<zap(1,pot+1,pot*2+1,a+pot,b+pot)<<"\n";
        }
        return 0;
    }

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