Submission #78121

#	Time	Username	Problem	Language	Result	Execution time	Memory
78121		nxteru	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	250 ms	12620 KiB

sterilizing

#include <iostream>
#include <algorithm>
#include <set>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n,q,k,p[100005],bit[100005];
set<int>o;
void add(int a,ll x){
    while(a<=n){
        bit[a]+=x;
        a+=(a&-a);
    }
}
ll sum(int a){
    ll res=0;
    while(a>0){
        res+=bit[a];
        a-=(a&-a);
    }
    return res;
}
int main(void){
    scanf("%lld%lld%lld",&n,&q,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",p+i);
        add(i,p[i]);
        if(p[i]>0)o.insert(i);
    }
    while(q){
        ll s,a,b;
        scanf("%lld%lld%lld",&s,&a,&b);
        if(s==1){
            add(a,b-p[a]);
            p[a]=b;
            o.insert(a);
        }
        if(s==2&&k!=1){
            auto it=o.lower_bound(a);
            while(it!=o.end()&&*it<=b){
                add(*it,-p[*it]+p[*it]/k);
                p[*it]/=k;
                if(p[*it]==0){
                    auto itr=it;
                    it++;
                    o.erase(itr);
                }else it++;
            }
        }
        if(s==3){
            printf("%lld\n",sum(b)-sum(a-1));
        }
        q--;
    }
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&n,&q,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",p+i);
         ~~~~~^~~~~~~~~~~~
sterilizing.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&s,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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