Submission #1189504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189504		AlgorithmWarrior	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	1071 ms	271072 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

int const MAX=100005;
int n,q,divid;

struct AINT{
    deque<long long>v[4*MAX];
    int lazy[4*MAX];
    deque<long long>combine(deque<long long>a,deque<long long>b){
        deque<long long>comb;
        int i;
        for(i=0;i<(int)a.size() || i<(int)b.size();++i){
            long long nr=0;
            if(i<(int)a.size())
                nr+=a[i];
            if(i<(int)b.size())
                nr+=b[i];
            comb.push_back(nr);
        }
        return comb;
    }
    void propagate(int nod){
        if(lazy[nod]){
            int i;
            for(i=1;i<=lazy[nod] && v[2*nod][0];++i)
                v[2*nod].pop_front();
            for(i=1;i<=lazy[nod] && v[2*nod+1][0];++i)
                v[2*nod+1].pop_front();
            lazy[2*nod]+=lazy[nod];
            lazy[2*nod+1]+=lazy[nod];
            lazy[nod]=0;
        }
    }
    deque<long long>imparte(int nr){
        deque<long long>deq;
        deq.push_back(nr);
        if(divid!=1){
            while(nr){
                nr/=divid;
                deq.push_back(nr);
            }
        }
        return deq;
    }
    void point_update(int nod,int st,int dr,int poz,int val){
        if(st==dr)
            v[nod]=imparte(val);
        else{
            propagate(nod);
            int mij=(st+dr)/2;
            if(poz<=mij)
                point_update(2*nod,st,mij,poz,val);
            else
                point_update(2*nod+1,mij+1,dr,poz,val);
            v[nod]=combine(v[2*nod],v[2*nod+1]);
        }
    }
    void range_update(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b){
            if(v[nod][0])
                v[nod].pop_front();
            ++lazy[nod];
        }
        else{
            propagate(nod);
            int mij=(st+dr)/2;
            if(a<=mij)
                range_update(2*nod,st,mij,a,b);
            if(b>mij)
                range_update(2*nod+1,mij+1,dr,a,b);
            v[nod]=combine(v[2*nod],v[2*nod+1]);
        }
    }
    long long query(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            return v[nod][0];
        propagate(nod);
        int mij=(st+dr)/2;
        long long sum=0;
        if(a<=mij)
            sum+=query(2*nod,st,mij,a,b);
        if(b>mij)
            sum+=query(2*nod+1,mij+1,dr,a,b);
        return sum;
    }
}aint;

void read(){
    cin>>n>>q>>divid;
    int i;
    for(i=1;i<=n;++i){
        int nr;
        cin>>nr;
        aint.point_update(1,1,n,i,nr);
    }
}

void process_queries(){
    int i;
    for(i=1;i<=q;++i){
        int type;
        cin>>type;
        if(type==1){
            int poz,val;
            cin>>poz>>val;
            aint.point_update(1,1,n,poz,val);
        }
        else{
            int l,r;
            cin>>l>>r;
            if(type==2){
                if(divid!=1)
                    aint.range_update(1,1,n,l,r);
            }
            else
                cout<<aint.query(1,1,n,l,r)<<'\n';
        }
    }
}

int main()
{
    read();
    process_queries();
    return 0;
}

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