Submission #362562

#	Time	Username	Problem	Language	Result	Execution time	Memory
362562		denkendoemeer	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	887 ms	10544 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,v[100005];
set<int>st;
struct ain
{
    ll aint[270000];
    void update(int nod,int st,int dr,int poz,int val)
    {
        if (poz<st || poz>dr)
            return ;
        if (st==dr){
            aint[nod]=val;
            return ;
        }
        int mij=(st+dr)/2;
        update(nod*2,st,mij,poz,val);
        update(nod*2+1,mij+1,dr,poz,val);
        aint[nod]=aint[nod*2]+aint[nod*2+1];
    }
    ll query(int nod,int st,int dr,int l,int r)
    {
        if (dr<l || r<st)
            return 0;
        if (l<=st && dr<=r)
            return aint[nod];
        int mij=(st+dr)/2;
        return query(nod*2,st,mij,l,r)+query(nod*2+1,mij+1,dr,l,r);
    }
}ai;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int q,k,i;
    scanf("%d%d%d",&n,&q,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
        ai.update(1,1,n,i,v[i]);
        if (v[i])
            st.insert(i);
    }
    for(i=1;i<=q;i++){
        int tip,x,y;
        scanf("%d%d%d",&tip,&x,&y);
        if (tip==1){
            v[x]=y;
            ai.update(1,1,n,x,v[x]);
            if (v[x])
                st.insert(x);
        }
        if (tip==2){
            if (k==1)
                continue;
            auto l=st.lower_bound(x);
            auto r=st.upper_bound(y);
            vector<int>aux;
            while(l!=r){
                int val=*l;
                l++;
                v[val]/=k;
                ai.update(1,1,n,val,v[val]);
                if (v[val]==0)
                    aux.push_back(val);
            }
            for(auto it:aux)
                st.erase(it);
        }
        if (tip==3)
            printf("%lld\n",ai.query(1,1,n,x,y));
    }
return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d%d",&n,&q,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~
sterilizing.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |         scanf("%d%d%d",&tip,&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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