Submission #203342

#	Time	Username	Problem	Language	Result	Execution time	Memory
203342		nvmdava	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	186 ms	9592 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f

ll bit[N];
ll query(int x){
    ll w = 0;
    while(x){
        w += bit[x];
        x -= x & -x;
    }
    return w;
}
void update(int x, ll w){
    while(x < N){
        bit[x] += w;
        x += x & -x;
    }
}
set<int> in;
ll a[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q, k;
    cin>>n>>q>>k;
    for(int i = 1; i <= n; ++i){
        cin>>a[i];
        update(i, a[i]);
        if(a[i])
            in.insert(i);
    }

    while(q--){
        int t, l, r;
        cin>>t>>l>>r;
        if(t == 3)
            cout<<query(r) - query(l - 1)<<'\n';
        else if(t == 1){
            update(l, r - a[l]);
            if(a[l] && !r)
                in.erase(l);
            else if(!a[l] && r)
                in.insert(l);
            a[l] = r;
        } else {
            if(k == 1) continue;
            auto it = in.lower_bound(l);
            while(it != in.end() && *it <= r){
                auto f = it++;
                update(*f, a[*f] / k - a[*f]);
                a[*f] /= k;
                if(a[*f] == 0)
                    in.erase(f);
            }
        }
    }

}

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