Submission #916793

#	Time	Username	Problem	Language	Result	Execution time	Memory
916793		Dec0Dedd	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	100 ms	9040 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

struct fenwick {
    vector<ll> bit;
    int n;
 
    void init(int sz) {
        n=sz+10;
        bit.assign(n, 0);
    }
 
    ll sum(int r) {
        ll res=0;
        for (;r>=0; r=(r&(r+1))-1) res+=bit[r];
        return res;
    }
 
    ll que(int l, int r) {
        return sum(r)-sum(l-1);
    }
 
    void upd(int x, ll d) {
        for (; x<n; x=x|(x+1)) bit[x]+=d;
    }

    void st(int x, ll d) {
        ll vl=que(x, x);
        upd(x, d-vl);
    }
};

const int N = 1e5+10;

int n, q, k, c[N];

void solve() {
    cin>>n>>q>>k;
    for (int i=1; i<=n; ++i) cin>>c[i];

    fenwick f; f.init(n+10);

    set<int> st;
    for (int i=1; i<=n; ++i) {
        f.st(i, c[i]);
        if (c[i] > 0) st.insert(i);
    }

    while (q--) {
        int s, t, u; cin>>s>>t>>u;
        if (s == 1) {
            f.upd(t, u-c[t]);
            c[t]=u;
            if (u > 0) st.insert(t);
        } else if (s == 2) {
            auto ptr=st.lower_bound(t);
            if (k == 1) continue;

            while (ptr != st.end()) {
                if ((*ptr) > u) break;
                int nvl=c[*ptr]/k;
                f.upd(*ptr, nvl-c[*ptr]);
                c[*ptr]=nvl;
                
                if (nvl == 0) {
                    st.erase(ptr++);
                    continue;
                } ++ptr;
            }
        } else cout<<f.que(t, u)<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int t=1; //cin>>t;
    while (t--) solve();
}

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