Submission #581836

#	Time	Username	Problem	Language	Result	Execution time	Memory
581836		Jarif_Rahman	Sterilizing Spray (JOI15_sterilizing)	C++17	0 / 100	5051 ms	144764 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 segtree{
    struct node{
        ll 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;
            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;

    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";
        }
    }
}

Compilation message (stderr)

sterilizing.cpp: In constructor 'segtree::segtree(int)':
sterilizing.cpp:47:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   47 |         while(k < n) k*=2; k*=2;
      |         ^~~~~
sterilizing.cpp:47:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   47 |         while(k < n) k*=2; k*=2;
      |                            ^

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