Submission #483676

#	Time	Username	Problem	Language	Result	Execution time	Memory
483676		Mahfel	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	3262 ms	77796 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 2e5 + 20 , LOG = 35;
#define lt(x) 2*x+1
#define rt(x) 2*x+2
int n,q,k;
int a[MXN];

struct seg_tree {
    int size;
    vector<ll> v[LOG] , d;
    seg_tree() {
        size = 0;
    }
    void init() {
        size = 1;
        while(size < n) size <<= 1;
        for(int i = 0 ; i < LOG ; i++) v[i].assign(2*size , 0);
        d.assign(2*size , 0);
    }
    void build(int x , int lx , int rx) {
        if(rx-lx == 1) {
            if(lx < n) {
                v[0][x] = a[lx];
                for(int i = 1 ; i < LOG ; i++) {
                    v[i][x] = v[i-1][x]/k;
                }
            }
            return;
        }
        int m = (lx+rx)/2;
        build(lt(x) , lx , m); build(rt(x) , m , rx);
        for(int i = 0 ; i < LOG ; i++) {
            v[i][x] = v[i][lt(x)] + v[i][rt(x)];
        }
    }
    void build() {
        build(0 , 0 , size);
    }

    void shift(int x , int lx , int rx) {
        if(rx-lx == 1) return;
        d[lt(x)] += d[x];
        d[rt(x)] += d[x];
    }
    void update(int x , int lx , int rx) {
        for(int i = 0 ; i < LOG ; i++) {
            v[i][x] = (i+d[x] < LOG ? v[i+d[x]][x] : 0);
        }
        d[x] = 0;
    }

    void set(int x , int lx , int rx , int i , ll t) {
        if(rx-lx == 1) {
            v[0][x] = t;
            for(int i = 1 ; i < LOG ; i++) {
                v[i][x] = v[i-1][x]/k;
            }
            d[x] = 0;
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        if(i < m) {
            set(lt(x) , lx , m , i , t);
            shift(rt(x) , m , rx); update(rt(x) , m , rx);
        } else {
            set(rt(x) , m , rx , i , t);
            shift(lt(x) , lx , m); update(lt(x) , lx , m);
        }
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
    }
    void set(int i , ll k) {
        set(0 , 0 , size , i , k);
    }

    void divide(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            d[x]++;
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        divide(lt(x) , lx , m , l , r);
        divide(rt(x) , m , rx , l , r);
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
    }
    void divide(int l , int r) {
        divide(0 , 0 , size , l , r);
    }

    ll sum(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return d[x] >= LOG ? 0 : v[d[x]][x];
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return 0;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        ll a = sum(lt(x) , lx , m , l , r) , b = sum(rt(x) , m , rx , l , r);
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
        return a+b;
    }
    ll sum(int l , int r) {
        return sum(0 , 0 , size , l , r);
    }
} seg;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> q >> k;
    for(int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    seg.init(); seg.build();

    while(q--) {

        int type,x,y; cin >> type >> x >> y;
        if(type == 1) {
            seg.set(x-1 , y);
        }
        if(type == 2) {
            if(k > 1) seg.divide(x-1 , y);
        }
        if(type == 3) {
            cout << seg.sum(x-1 , y) << "\n";
        }

    }

}

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