Submission #1130588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130588		lopkus	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	463 ms	9060 KiB

sterilizing

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 5;

set<int> s;

struct segtree{
    int t[4*N];
    int query(int v,int tl,int tr,int l,int r){
        if(tl>r||tr<l)return 0;
        if(tl>=l&&tr<=r)return t[v];
        int tm=(tl+tr)/2;
        return (query(v*2,tl,tm,l,r)+query(v*2+1,tm+1,tr,l,r));
    }
    void update(int v,int tl,int tr,int index,int value){
        if(tl==tr)t[v]=value;
        else {
            int tm=(tl+tr)/2;
            if(index<=tm)update(v*2,tl,tm,index,value);
            else update(v*2+1,tm+1,tr,index,value);
            t[v]=(t[v*2]+t[v*2+1]);
        }
    }
}seg;


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q, k;
    cin >> n >> q >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(a[i] > 0) {
            s.insert(i);
        }
        seg.update(1, 1, n, i, a[i]);
    }
    while(q--) {
        int o;
        cin >> o;
        if(o == 1) {
            int index, value;
            cin >> index >> value;
            if(a[index] > 0) {
                s.erase(index);
            }
            seg.update(1, 1, n, index, value);
            a[index] = value;
            if(a[index] > 0) {
                s.insert(index);
            }
        }
        else if(o == 2) {
            int l, r;
            cin >> l >> r;
            if(k == 1) {
                continue;
            }
            auto it = s.lower_bound(l);
            vector<int> tmp;
            while(it != s.end() && *it <= r) {
                a[*it] /= k;
                if(a[*it] == 0) {
                    tmp.push_back(*it);
                }
                seg.update(1, 1, n, *it, a[*it]);
                it++;
            }
            for(auto it : tmp) {
                s.erase(it);
            }
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << seg.query(1, 1, n, l, r) << "\n";
        }
    }
}

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