oj.uz

Submission #475480

# Submission time Handle Problem Language Result Execution time Memory
475480 2021-09-22T15:30:50 Z nicolaalexandra Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 852 ms 71632 KB 
#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 shift (int nod, int val){
    for (int i=0;i<max_exp;i++){
        if (i + val < max_exp)
            aint[nod].v[i] = aint[nod].v[i+val];
        else aint[nod].v[i] = 0;
    }
}

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;
        }

        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;

        shift (fiu_st,val);
        shift (fiu_dr,val);

        /*
        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){

        shift (nod,1);

        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 1356 KB Output is correct
4 Correct 12 ms 1388 KB Output is correct
5 Correct 20 ms 2528 KB Output is correct
6 Correct 15 ms 2532 KB Output is correct
7 Correct 17 ms 2508 KB Output is correct
8 Correct 15 ms 2520 KB Output is correct
9 Correct 16 ms 2516 KB Output is correct
10 Correct 16 ms 2508 KB Output is correct
11 Correct 15 ms 2488 KB Output is correct
12 Correct 16 ms 2524 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 2140 KB Output is correct
2 Correct 180 ms 1988 KB Output is correct
3 Correct 142 ms 3236 KB Output is correct
4 Correct 181 ms 3460 KB Output is correct
5 Correct 221 ms 3568 KB Output is correct
6 Correct 214 ms 3572 KB Output is correct
7 Correct 206 ms 3512 KB Output is correct
8 Correct 213 ms 3764 KB Output is correct
9 Correct 217 ms 3688 KB Output is correct
10 Correct 203 ms 3588 KB Output is correct
11 Correct 200 ms 3652 KB Output is correct
12 Correct 210 ms 3648 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 4600 KB Output is correct
2 Correct 130 ms 34696 KB Output is correct
3 Correct 184 ms 34872 KB Output is correct
4 Correct 551 ms 18628 KB Output is correct
5 Correct 831 ms 70236 KB Output is correct
6 Correct 783 ms 70200 KB Output is correct
7 Correct 214 ms 4672 KB Output is correct
8 Correct 811 ms 70468 KB Output is correct
9 Correct 623 ms 70104 KB Output is correct
10 Correct 613 ms 70076 KB Output is correct
11 Correct 582 ms 70124 KB Output is correct
12 Correct 644 ms 70232 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 34700 KB Output is correct
2 Correct 634 ms 36360 KB Output is correct
3 Correct 345 ms 35784 KB Output is correct
4 Correct 594 ms 19488 KB Output is correct
5 Correct 847 ms 71436 KB Output is correct
6 Correct 845 ms 71504 KB Output is correct
7 Correct 852 ms 71424 KB Output is correct
8 Correct 844 ms 71632 KB Output is correct
9 Correct 638 ms 71392 KB Output is correct
10 Correct 625 ms 71404 KB Output is correct
11 Correct 630 ms 71304 KB Output is correct
12 Correct 634 ms 71480 KB Output is correct