Submission #523863

#	Time	Username	Problem	Language	Result	Execution time	Memory
523863		IMystic	Sterilizing Spray (JOI15_sterilizing)	C++17	0 / 100	5064 ms	7868 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]);
    }
};
 
 
int op(int a, int b){
    return (a + b);
}
 
int 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<int, 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);
            b.insert(l);
        }else if(t == 2){
            while(true){
                auto it = b.lower_bound(l);
                if(it == b.end() || *it >= r)break;
                int tem = d.get(*it)/k;
                d.set(*it, tem);
                l = *it + 1;
                if(tem == 0)b.erase(it);
            }
        }else {
            cout << d.get(l, r) << '\n';
        }
    }
 
    return 0;
}

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