제출 #375660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375660		ritul_kr_singh	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	1301 ms	70124 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75