Submission #523887

#	Time	Username	Problem	Language	Result	Execution time	Memory
523887		IMystic	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	477 ms	8120 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;

template <class S, S (*op)(S, S), S I() > 
class segment {
 public : 
    explicit segment(vector<int> &a) : n(int(a.size())) {
        log = 1;
        while((1<<log) < n)++log;
        size = 1<<log;
        d.resize(2*size, I());
        for(int i=0; i<n; i++)d[i + size] = a[i];
        for(int i=size - 1; i > 0; i--)update(i);
    }

    void set(int k, S v){
        assert(0 <= k && k < n);
        k += size;
        d[k] = v;
        for(int i = 1; i <= log; i++)update(k>>i);
    }

    S get(int k){
        assert(0 <= k && k < n);
        k += size;
        return d[k];
    }

    S get(int l, int r){
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return I();
        l += size;
        r += size;

        
        S sml = I(), smr = I();
        while(l < r){
            if(l&1)sml = op(sml, d[l++]);
            if(r&1)smr = op(d[--r], smr);

            l >>= 1;
            r >>= 1;
        }
        
        return op(sml, smr);
    }
 private :
    int n, log, size;
    vector<S> d;

    void update(int p){
        d[p] = op(d[2*p], d[2*p + 1]);
    }
};


ll op(ll a, ll b){
    return (a + b);
}

ll I(){
    return 0;
}

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

    int n, q, k;
    cin >> n >> q >> k;

    vector<int> a(n);
    for(int i=0; i<n; i++)cin >> a[i];

    segment<ll, op, I> d(a);
    set<int> b;
    for(int i=0; i<n; i++)b.insert(i);

    for(int i=0; i<q; i++){
        int t, l, r;
        cin >> t >> l >> r;
        --l;
        if(t == 1){
            d.set(l, r);
            if(r > 0)b.insert(l);
        }else if(t == 2){
            if(k == 1)continue;
            vector<int> tem ;
            for(auto it = lower_bound(b.begin(), b.end(), l); it != b.end() && (*it) < r; it++){
                int x = *it;
                d.set(x, d.get(x)/k);
                if(d.get(x) == 0)tem.push_back(x);
            }
            for(int &c : tem)b.erase(c);
        }else {
            cout << d.get(l, r) << '\n';
        }
        // for(int i = 0; i < n; i++)cout << d.get(i) << ' ';
        // cout << '\n';
    }

    return 0;
}

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