Submission #219263

#	Time	Username	Problem	Language	Result	Execution time	Memory
219263		MKopchev	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	1485 ms	9336 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

int n,q,k,inp[nmax];

long long fenwick[nmax];
void update(int pos,int val)
{
    while(pos<=n)
    {
        fenwick[pos]+=val;
        pos=pos+(pos&(-pos));
    }
}
long long sum(int pos)
{
    long long ret=0;
    while(pos)
    {
        ret=ret+fenwick[pos];
        pos=pos-(pos&(-pos));
    }
    return ret;
}
long long query(int l,int r)
{
    return sum(r)-sum(l-1);
}

set<int> non_zero;
void make(int pos,int val)
{
    //cout<<"make "<<pos<<" "<<val<<endl;

    if(inp[pos])non_zero.erase(pos);
    update(pos,-inp[pos]);

    inp[pos]=val;
    if(inp[pos])non_zero.insert(pos);
    update(pos,inp[pos]);
}

int main()
{
    scanf("%i%i%i",&n,&q,&k);

    for(int i=1;i<=n;i++)
    {
        scanf("%i",&inp[i]);

        int was=inp[i];
        inp[i]=0;

        make(i,was);

        if(inp[i])non_zero.insert(i);
    }

    int type,l,r;
    for(int i=1;i<=q;i++)
    {
        scanf("%i%i%i",&type,&l,&r);
        if(type==1)
        {
            make(l,r);
        }
        if(type==2&&k!=1)
        {
            int lst_used=l-1;
            while(1)
            {
                set<int>::iterator it=non_zero.upper_bound(lst_used);
                if(it==non_zero.end())break;

                int current=*it;
                if(current>r)break;

                make(current,inp[current]/k);
                lst_used=current;
            }
        }
        if(type==3)
        {
            printf("%lld\n",query(l,r));
        }
        /*
        for(int j=1;j<=n;j++)
            cout<<query(j,j)<<" ";cout<<endl;
        cout<<"---"<<endl;
        */
    }
    return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&q,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&type,&l,&r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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