Submission #1168109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168109		altern23	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	122 ms	7840 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 998244353;

struct BIT{
    ll n;
    vector<ll> bit;
    BIT (ll _n){
        n = _n;
        bit.resize(n + 5);
    }
    void upd(ll idx, ll val) { for(int i = idx; i <= n; i += i & -i) bit[i] += val; }
    ll get(ll idx){ ll ans = 0; for(int i = idx; i >= 1; i -= i & -i) ans += bit[i]; return ans; }
    ll query(ll l, ll r){ return get(r) - get(l - 1); }
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, q, k; cin >> n >> q >> k;
        vector<ll> a(n + 5);
        set<ll> st;
        BIT bit(n);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            bit.upd(i, a[i]);
            if(a[i]) st.insert(i);
        }

        for(int i = 1; i <= q; i++){
            ll s, t, u; cin >> s >> t >> u;
            if(s == 1){
                if(u == 0){
                    if(st.find(t) != st.end()) st.erase(t);
                }
                else st.insert(t);
                bit.upd(t, u - a[t]);
                a[t] = u;
            }
            else if(s == 2){
                if(k == 1) continue;
                vector<ll> del;
                for(auto x = st.lower_bound(t); x != st.end() && (*x) <= u; x++){
                    bit.upd((*x), a[*x] / k - a[*x]);
                    a[*x] /= k;
                    if(!a[*x]) del.push_back(*x);
                }
                for(auto x : del) st.erase(x);
            }
            else{
                cout << bit.query(t, u) << "\n";
            }
        }
    }   
}

/*

*/ 

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