oj.uz

Submission #375660

# Submission time Handle Problem Language Result Execution time Memory
375660 2021-03-09T16:20:13 Z ritul_kr_singh Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1301 ms 70124 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

int n, q, k;
vector<int> init;

struct segtree{
    int sz = 1;
    vector<array<int, 31>> sums;
    array<int, 31> ID = {};
    vector<int> ops;
    void pull(int x){
        for(int i=0; i<31; ++i) sums[x][i] = sums[2*x+1][i] + sums[2*x+2][i];
        shift(sums[x], ops[x]);
    }
    void shift(array<int, 31> &c, int y){
        for(int i=0; i<31; ++i) c[i] = (i+y) < 31 ? c[i+y] : 0;
    }
    void push(int x){
        if(x+1<sz){
            ops[2*x+1] += ops[x];
            shift(sums[2*x+1], ops[x]);
            ops[2*x+2] += ops[x];
            shift(sums[2*x+2], ops[x]);
            ops[x] = 0;
            pull(x);
        }
    }
    segtree(){
        while(sz < n) sz *= 2;
        sums.assign(2*sz, ID);
        ops.assign(2*sz, 0);
        build(0, 0, sz);
    }
    void build(int x, int lx, int rx){
        if(rx-lx==1){
            if(lx>=n) return;
            for(int i=0; i<31; ++i){
                sums[x][i] = init[lx]%k;
                init[lx] /= k;
            }
            if(k==1) sums[x][0] = init[lx];
            return;
        }
        int mx = (lx+rx)/2;
        build(2*x+1, lx, mx);
        build(2*x+2, mx, rx);
        pull(x);
    }
    void divide(int l, int r, int x, int lx, int rx){
        push(x);
        if(r<=lx or rx<=l) return;
        if(l<=lx and rx<=r){
            ++ops[x];
            shift(sums[x], 1);
            return;
        }
        int mx = (lx+rx)/2;
        divide(l, r, 2*x+1, lx, mx);
        divide(l, r, 2*x+2, mx, rx);
        pull(x);
    }
    void divide(int l, int r){ divide(l, r+1, 0, 0, sz); }
    void set(int pos, int val, int x, int lx, int rx){
        push(x);
        if(rx-lx==1){
            for(int i=0; i<31; ++i){
                sums[x][i] = val%k;
                val /= k;
            }
            ops[x] = 0;
            if(k==1) sums[x][0] = val;
            return;
        }
        int mx = (lx+rx)/2;
        if(pos<mx) set(pos, val, 2*x+1, lx, mx);
        else set(pos, val, 2*x+2, mx, rx);
        pull(x);
    }
    void set(int pos, int val){ set(pos, val, 0, 0, sz); }
    array<int, 31> get(int l, int r, int x, int lx, int rx){
        push(x);
        if(r<=lx or rx<=l) return ID;
        if(l<=lx and rx<=r) return sums[x];
        int mx = (lx+rx)/2;
        auto resL = get(l, r, 2*x+1, lx, mx), resR = get(l, r, 2*x+2, mx, rx);
        for(int i=0; i<31; ++i) resL[i] += resR[i];
        return resL;
    }
    int get(int l, int r){
        auto arr = get(l, r+1, 0, 0, sz);
        int res = 0;
        for(int i=0, mul=1; i<31 and mul<(int)1e11; ++i, mul*=k) res += arr[i]*mul;
        return res;
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q >> k;
    init.resize(n);
    for(int &i : init) cin >> i;

    segtree st;

    while(q--){
        int s, t, u; cin >> s >> t >> u;
        if(s==1){
            st.set(t-1, u);
        }else if(s==2){
            if(k>1) st.divide(t-1, u-1);
        }else{
            cout << st.get(t-1, u-1) nl;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 492 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 4 ms 1388 KB Output is correct
4 Correct 22 ms 1516 KB Output is correct
5 Correct 26 ms 2540 KB Output is correct
6 Correct 23 ms 2540 KB Output is correct
7 Correct 23 ms 2540 KB Output is correct
8 Correct 23 ms 2540 KB Output is correct
9 Correct 24 ms 2540 KB Output is correct
10 Correct 23 ms 2540 KB Output is correct
11 Correct 30 ms 2540 KB Output is correct
12 Correct 23 ms 2540 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 34156 KB Output is correct
2 Correct 568 ms 35636 KB Output is correct
3 Correct 491 ms 68716 KB Output is correct
4 Correct 615 ms 69484 KB Output is correct
5 Correct 769 ms 69804 KB Output is correct
6 Correct 760 ms 69740 KB Output is correct
7 Correct 803 ms 70124 KB Output is correct
8 Correct 755 ms 69740 KB Output is correct
9 Correct 780 ms 69612 KB Output is correct
10 Correct 771 ms 69740 KB Output is correct
11 Correct 715 ms 69740 KB Output is correct
12 Correct 720 ms 69612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 4588 KB Output is correct
2 Correct 195 ms 33720 KB Output is correct
3 Correct 293 ms 33644 KB Output is correct
4 Correct 913 ms 17260 KB Output is correct
5 Correct 1241 ms 67252 KB Output is correct
6 Correct 1218 ms 67180 KB Output is correct
7 Correct 701 ms 67052 KB Output is correct
8 Correct 1277 ms 68332 KB Output is correct
9 Correct 1091 ms 68312 KB Output is correct
10 Correct 1139 ms 68204 KB Output is correct
11 Correct 1152 ms 68540 KB Output is correct
12 Correct 1174 ms 68460 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 34028 KB Output is correct
2 Correct 911 ms 33948 KB Output is correct
3 Correct 560 ms 33668 KB Output is correct
4 Correct 1004 ms 17388 KB Output is correct
5 Correct 1223 ms 67308 KB Output is correct
6 Correct 1223 ms 67176 KB Output is correct
7 Correct 1234 ms 67180 KB Output is correct
8 Correct 1301 ms 67224 KB Output is correct
9 Correct 1158 ms 67316 KB Output is correct
10 Correct 1155 ms 67436 KB Output is correct
11 Correct 1135 ms 67436 KB Output is correct
12 Correct 1128 ms 67180 KB Output is correct