Submission #475477

#	Time	Username	Problem	Language	Result	Execution time	Memory
475477		nicolaalexandra	Sterilizing Spray (JOI15_sterilizing)	C++14	10 / 100	491 ms	34732 KiB

sterilizing

#include <bits/stdc++.h>
#define DIM 100010
#define INF 1000000000000000LL
using namespace std;

const int max_exp = 32;

struct segment_tree{
    long long v[max_exp];
    int lazy;
} aint[DIM*4];

int n,k,q,i,j,x,y,tip;
long long sol[max_exp],v[DIM],p[max_exp],aint2[DIM*4];

void update_nod (int nod){
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    for (int i=0;i<max_exp;i++)
        aint[nod].v[i] = aint[fiu_st].v[i] + aint[fiu_dr].v[i];
}

void build (int nod, int st, int dr){

    if (st == dr){
        long long val = v[st];
        for (int i=0;i<max_exp;i++){
            aint[nod].v[i] = val % k;
            val /= k;
        }

        /*
        long long val = v[st];
        for (int i=max_exp;i>=0;i--){
            aint[nod].v[i] = val / p[i];
            val -= aint[nod].v[i] * p[i];
        }
        */

        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    update_nod (nod);
}

void update_lazy (int nod, int st, int dr){
    if (!aint[nod].lazy)
        return;
    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
        int val = aint[nod].lazy;
        for (int i=0;i+val<max_exp;i++){
            aint[fiu_st].v[i] = aint[fiu_st].v[i + val];
            aint[fiu_dr].v[i] = aint[fiu_dr].v[i + val];
        }

        for (int i=max_exp-val;i<max_exp;i++)
            aint[fiu_st].v[i] = aint[fiu_dr].v[i] = 0;


        aint[fiu_st].lazy += val;
        aint[fiu_dr].lazy += val;
    }
    aint[nod].lazy = 0;
}

void update_intv (int nod, int st, int dr, int x, int y){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){

        for (int i=0;i<max_exp-1;i++)
            aint[nod].v[i] = aint[nod].v[i+1];
        aint[nod].v[max_exp-1] = 0;

        aint[nod].lazy++;

        update_lazy (nod,st,dr);

        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update_intv (nod<<1,st,mid,x,y);
    if (y > mid)
        update_intv ((nod<<1)|1,mid+1,dr,x,y);

    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    update_nod(nod);
}

void update (int nod, int st, int dr, int poz, long long val){
    update_lazy (nod,st,dr);
    if (st == dr){

        for (int i=0;i<max_exp;i++){
            aint[nod].v[i] = val % k;
            val /= k;
        }

        return;
    }

    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    update_nod (nod);
}

void query (int nod, int st, int dr, int x, int y){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){

        for (int i=0;i<max_exp;i++)
            sol[i] += aint[nod].v[i];

        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}

void build2 (int nod, int st, int dr){
    if (st == dr){
        aint2[nod] = v[st];
        return;
    }

    int mid = (st+dr)>>1;
    build2 (nod<<1,st,mid);
    build2 ((nod<<1)|1,mid+1,dr);

    aint2[nod] = aint2[nod<<1] + aint2[(nod<<1)|1];
}

void update2 (int nod, int st, int dr, int poz, long long val){
    if (st == dr){
        aint2[nod] = val;
        return;
    }
    int mid = (st+dr)>>1;

    if (poz <= mid)
        update2(nod<<1,st,mid,poz,val);
    else update2((nod<<1)|1,mid+1,dr,poz,val);

    aint2[nod] = aint2[nod<<1] + aint2[(nod<<1)|1];
}

long long query2 (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y)
        return aint2[nod];
    int mid = (st+dr)>>1;
    long long sol_st = 0, sol_dr = 0;
    if (x <= mid)
        sol_st = query2(nod<<1,st,mid,x,y);
    if (y > mid)
        sol_dr = query2((nod<<1)|1,mid+1,dr,x,y);

    return sol_st + sol_dr;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>q>>k;
    for (i=1;i<=n;i++)
        cin>>v[i];


    if (k == 1){

        build2 (1,1,n);
        for (;q--;){
            cin>>tip>>x>>y;
            if (tip == 1)
                update2 (1,1,n,x,y);
            else {
                if (tip == 3)
                    cout<<query2 (1,1,n,x,y)<<"\n";
            }
        }


        return 0;
    }


    p[0] = 1;
    for (i=1;i<=max_exp;i++){
        if (p[i-1] >  INF / k)
            break;

        p[i] = p[i-1] * k;
    }

    build (1,1,n);

    for (;q--;){

        cin>>tip>>x>>y;
        if (tip == 1)
            update (1,1,n,x,y);
        else {
            if (tip == 2)
                update_intv (1,1,n,x,y);
            else {
                for (int i=0;i<max_exp;i++)
                    sol[i] = 0;
                query (1,1,n,x,y);

                long long ans = 0;
                for (int i=0;i<max_exp;i++)
                    ans += p[i] * sol[i];

                cout<<ans<<"\n";
            }
        }

    }


    return 0;
}

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