oj.uz

Submission #483676

# Submission time Handle Problem Language Result Execution time Memory
483676 2021-10-31T15:31:22 Z Mahfel Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 3262 ms 77796 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 2e5 + 20 , LOG = 35;
#define lt(x) 2*x+1
#define rt(x) 2*x+2
int n,q,k;
int a[MXN];

struct seg_tree {
    int size;
    vector<ll> v[LOG] , d;
    seg_tree() {
        size = 0;
    }
    void init() {
        size = 1;
        while(size < n) size <<= 1;
        for(int i = 0 ; i < LOG ; i++) v[i].assign(2*size , 0);
        d.assign(2*size , 0);
    }
    void build(int x , int lx , int rx) {
        if(rx-lx == 1) {
            if(lx < n) {
                v[0][x] = a[lx];
                for(int i = 1 ; i < LOG ; i++) {
                    v[i][x] = v[i-1][x]/k;
                }
            }
            return;
        }
        int m = (lx+rx)/2;
        build(lt(x) , lx , m); build(rt(x) , m , rx);
        for(int i = 0 ; i < LOG ; i++) {
            v[i][x] = v[i][lt(x)] + v[i][rt(x)];
        }
    }
    void build() {
        build(0 , 0 , size);
    }

    void shift(int x , int lx , int rx) {
        if(rx-lx == 1) return;
        d[lt(x)] += d[x];
        d[rt(x)] += d[x];
    }
    void update(int x , int lx , int rx) {
        for(int i = 0 ; i < LOG ; i++) {
            v[i][x] = (i+d[x] < LOG ? v[i+d[x]][x] : 0);
        }
        d[x] = 0;
    }

    void set(int x , int lx , int rx , int i , ll t) {
        if(rx-lx == 1) {
            v[0][x] = t;
            for(int i = 1 ; i < LOG ; i++) {
                v[i][x] = v[i-1][x]/k;
            }
            d[x] = 0;
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        if(i < m) {
            set(lt(x) , lx , m , i , t);
            shift(rt(x) , m , rx); update(rt(x) , m , rx);
        } else {
            set(rt(x) , m , rx , i , t);
            shift(lt(x) , lx , m); update(lt(x) , lx , m);
        }
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
    }
    void set(int i , ll k) {
        set(0 , 0 , size , i , k);
    }

    void divide(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            d[x]++;
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        divide(lt(x) , lx , m , l , r);
        divide(rt(x) , m , rx , l , r);
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
    }
    void divide(int l , int r) {
        divide(0 , 0 , size , l , r);
    }

    ll sum(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return d[x] >= LOG ? 0 : v[d[x]][x];
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return 0;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        ll a = sum(lt(x) , lx , m , l , r) , b = sum(rt(x) , m , rx , l , r);
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
        return a+b;
    }
    ll sum(int l , int r) {
        return sum(0 , 0 , size , l , r);
    }
} seg;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> q >> k;
    for(int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    seg.init(); seg.build();

    while(q--) {

        int type,x,y; cin >> type >> x >> y;
        if(type == 1) {
            seg.set(x-1 , y);
        }
        if(type == 2) {
            if(k > 1) seg.divide(x-1 , y);
        }
        if(type == 3) {
            cout << seg.sum(x-1 , y) << "\n";
        }

    }

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 432 KB Output is correct
2 Correct 4 ms 844 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 13 ms 1536 KB Output is correct
5 Correct 15 ms 2708 KB Output is correct
6 Correct 15 ms 2628 KB Output is correct
7 Correct 15 ms 2716 KB Output is correct
8 Correct 16 ms 2636 KB Output is correct
9 Correct 15 ms 2712 KB Output is correct
10 Correct 19 ms 2708 KB Output is correct
11 Correct 16 ms 2716 KB Output is correct
12 Correct 17 ms 2636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1587 ms 38544 KB Output is correct
2 Correct 1451 ms 39840 KB Output is correct
3 Correct 1162 ms 76528 KB Output is correct
4 Correct 1432 ms 77300 KB Output is correct
5 Correct 1865 ms 77748 KB Output is correct
6 Correct 1829 ms 77796 KB Output is correct
7 Correct 1799 ms 77636 KB Output is correct
8 Correct 1716 ms 77640 KB Output is correct
9 Correct 1746 ms 77520 KB Output is correct
10 Correct 1921 ms 77572 KB Output is correct
11 Correct 1967 ms 77512 KB Output is correct
12 Correct 1909 ms 77532 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 5568 KB Output is correct
2 Correct 450 ms 37832 KB Output is correct
3 Correct 696 ms 37956 KB Output is correct
4 Correct 2244 ms 19524 KB Output is correct
5 Correct 2837 ms 75364 KB Output is correct
6 Correct 2790 ms 75336 KB Output is correct
7 Correct 1749 ms 75380 KB Output is correct
8 Correct 2831 ms 76120 KB Output is correct
9 Correct 3077 ms 76104 KB Output is correct
10 Correct 3142 ms 75996 KB Output is correct
11 Correct 3262 ms 76000 KB Output is correct
12 Correct 3179 ms 75988 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1819 ms 38148 KB Output is correct
2 Correct 2077 ms 38372 KB Output is correct
3 Correct 1257 ms 38312 KB Output is correct
4 Correct 2205 ms 19740 KB Output is correct
5 Correct 2827 ms 75592 KB Output is correct
6 Correct 2767 ms 75672 KB Output is correct
7 Correct 2766 ms 75388 KB Output is correct
8 Correct 2762 ms 75680 KB Output is correct
9 Correct 3111 ms 75588 KB Output is correct
10 Correct 3085 ms 75612 KB Output is correct
11 Correct 3136 ms 75496 KB Output is correct
12 Correct 3087 ms 75664 KB Output is correct