oj.uz

Submission #375656

# Submission time Handle Problem Language Result Execution time Memory
375656 2021-03-09T16:15:31 Z ritul_kr_singh Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 1293 ms 70008 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;
            }
            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;
            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){
            st.divide(t-1, u-1);
        }else{
            cout << st.get(t-1, u-1) nl;
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 492 KB Output is correct
2 Incorrect 7 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1128 ms 35664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 4936 KB Output is correct
2 Correct 198 ms 33772 KB Output is correct
3 Correct 295 ms 33900 KB Output is correct
4 Correct 894 ms 18296 KB Output is correct
5 Correct 1229 ms 68460 KB Output is correct
6 Correct 1210 ms 68332 KB Output is correct
7 Incorrect 1293 ms 68428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 35276 KB Output is correct
2 Correct 928 ms 35692 KB Output is correct
3 Correct 541 ms 34904 KB Output is correct
4 Correct 975 ms 19344 KB Output is correct
5 Correct 1279 ms 69620 KB Output is correct
6 Correct 1206 ms 69840 KB Output is correct
7 Correct 1196 ms 70008 KB Output is correct
8 Correct 1206 ms 69944 KB Output is correct
9 Correct 1109 ms 69656 KB Output is correct
10 Correct 1208 ms 69664 KB Output is correct
11 Correct 1090 ms 69392 KB Output is correct
12 Correct 1108 ms 69612 KB Output is correct