Submission #141115

#	Time	Username	Problem	Language	Result	Execution time	Memory
141115		rzbt	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	832 ms	11252 KiB

sterilizing

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

ll n,q,k;
ll niz[MAXN],seg[4*MAXN];
set<ll> s;

void dodaj(ll l,ll d,ll p,ll x,ll k){
    if(l==d){
        seg[k]=x;
        return;
    }
    ll mid=(l+d)/2;
    if(p<=mid)dodaj(l,mid,p,x,k+k);
    else dodaj(mid+1,d,p,x,k+k+1);
    seg[k]=seg[k+k]+seg[k+k+1];
}
ll dobij(ll l,ll d,ll tl,ll td,ll k){
    //printf("     %lld %lld    %lld %lld\n",l,d,k,seg[k]);
    if(l>td || d<tl)return 0;
    if(l>=tl && d<=td)return seg[k];
    ll mid=(l+d)/2;
    return dobij(l,mid,tl,td,k+k)+dobij(mid+1,d,tl,td,k+k+1);
}
vector<ll> zab;


int main()
{
    scanf("%lld %lld %lld", &n, &q, &k);
    for(ll i=1;i<=n;i++){
        scanf("%lld",niz+i);
        if(niz[i]!=0){
            s.insert(i);
        }
        dodaj(1,n,i,niz[i],1);
    }
    while(q--){
        ll qt,a,b;
        scanf("%lld %lld %lld", &qt, &a, &b);
        if(qt==1){
            niz[a]=b;
            if(niz[a]!=0){
                s.insert(a);
            }
            dodaj(1,n,a,niz[a],1);
        }else if(qt==2){
            if(k==1)continue;
            for(auto it=s.lower_bound(a);it!=s.end() && (*it)<=b;++it){

                ll t=*it;
                niz[t]/=k;
                if(niz[t]==0)zab.pb(t);
                dodaj(1,n,t,niz[t],1);
            }
            for(auto x:zab)s.erase(x);
            zab.clear();
        }else{
            printf("%lld\n",dobij(1,n,a,b,1));
        }

    }
    return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:39: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:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",niz+i);
         ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &qt, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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