Submission #582037

#	Time	Username	Problem	Language	Result	Execution time	Memory
582037		Jarif_Rahman	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	2593 ms	285004 KiB

sterilizing

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int K, C;

struct BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, ll x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    ll sum(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    ll sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
};

struct segtree{
    struct node{
        int divisions;
        deque<ll> d;
        node(){
            divisions = 0;
            d.assign(C, 0);
        }
        node(ll x){
            divisions = 0;
            d.assign(C, 0);
            for(int i = 0; i < C; i++){
                d[i] = x%K;
                x/=K;
            }
            reverse(d.begin(), d.end());
        }
        node operator+(node &a){
            node rt;
            for(int i = 0; i < C; i++) rt.d[i] = d[i]+a.d[i];
            return rt;
        }
        void pushdown_from(node &p){
            int x = p.divisions;
            divisions+=x;
            if(x >= C) d.assign(C, 0);
            else{
                while(x--) d.pop_back(), d.push_front(0);
            } 
        }
    };

    int k;
    vector<node> v;

    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
        v.assign(k, node());
    }

    void update(int in, int nd, int a, int b, ll x){
        if(a == b){
            v[nd] = node(x);
            return;
        }
        int md = (a+b)/2;

        v[2*nd].pushdown_from(v[nd]);
        v[2*nd+1].pushdown_from(v[nd]);
        v[nd].divisions = 0;

        if(in <= md) update(in, 2*nd, a, md, x);
        else update(in, 2*nd+1, md+1, b, x);

        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void update(int in, ll x){
        update(in, 1, 0, k/2-1, x);
    }

    void spray(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            v[nd].d.pop_back();
            v[nd].d.push_front(0);
            v[nd].divisions++;
            return;
        }

        int md = (a+b)/2;

        v[2*nd].pushdown_from(v[nd]);
        v[2*nd+1].pushdown_from(v[nd]);
        v[nd].divisions = 0;

        spray(l, r, 2*nd, a, md);
        spray(l, r, 2*nd+1, md+1, b);
        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void spray(int l, int r){
        spray(l, r, 1, 0, k/2-1);
    }

    ll sum(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return 0;
        if(a >= l && b <= r){
            ll p = 1, s = 0;
            for(int i = C-1; i >= 0; i--) s+=v[nd].d[i]*p, p*=K;
            return s;
        }

        int md = (a+b)/2;

        v[2*nd].pushdown_from(v[nd]);
        v[2*nd+1].pushdown_from(v[nd]);
        v[nd].divisions = 0;

        ll rt = sum(l, r, 2*nd, a, md) + sum(l, r, 2*nd+1, md+1, b);
        v[nd] = v[2*nd]+v[2*nd+1];
        return rt;
    }
    ll sum(int l, int r){
        return sum(l, r, 1, 0, k/2-1);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q >> K;

    if(K == 1){
        BIT bit(n);
        for(int i = 0; i < n; i++){
            ll x; cin >> x;
            bit.add(i, x);
        }
        while(q--){
            int tt; cin >> tt;
            if(tt == 1){
                int in; ll x; cin >> in >> x; in--;
                bit.add(in, x-bit.sum(in, in));
            }
            if(tt == 2){
                int l, r; cin >> l >> r; l--, r--;
                //do nothing
            }
            if(tt == 3){
                int l, r; cin >> l >> r; l--, r--;
                cout << bit.sum(l, r) << "\n";
            }
        }
        exit(0);
    }

    ll p = 1; C = 0;
    while(p < ll(1e9)) p*=K, C++;

    segtree seg(n);

    for(int i = 0; i < n; i++){
        ll x; cin >> x;
        seg.update(i, x);
    }

    while(q--){
        int tt; cin >> tt;
        if(tt == 1){
            int in; ll x; cin >> in >> x; in--;
            seg.update(in, x);
        }
        if(tt == 2){
            int l, r; cin >> l >> r; l--, r--;
            seg.spray(l, r);
        }
        if(tt == 3){
            int l, r; cin >> l >> r; l--, r--;
            cout << seg.sum(l, r) << "\n";
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75