Submission #48577

#	Time	Username	Problem	Language	Result	Execution time	Memory
48577		MladenP	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	313 ms	8944 KiB

sterilizing

#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
set<int> s;
vector<int> izbaciti;
lld bit[MAXN], a[MAXN];
lld query(int idx) {
    lld rez = 0;
    for( ; idx > 0; idx -= idx&-idx) rez += bit[idx];
    return rez;
}
void update(int idx, lld val) {
    val -= a[idx]; a[idx] += val;
    for( ; idx < MAXN; idx += idx&-idx) bit[idx] += val;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    lld N, Q, K, a1; cin >> N >> Q >> K;
    for(int i = 1; i <= N; i++) {
        cin >> a1; update(i, a1);
        if(a[i] != 0) s.insert(i);
    }
    while(Q--) {
        int type, u1, u2; cin >> type >> u1 >> u2;
        if(type == 1) {
            update(u1, u2);
            if(u2 != 0) s.insert(u1);
            else s.erase(u1);
        } else if(type == 2) {
            if(K == 1) continue;
            for(auto it = s.lower_bound(u1); it != s.end() && *it <= u2; it++) {
                update(*it, a[*it]/K);
                if(a[*it] == 0) izbaciti.pb(*it);
            }
            for(auto x : izbaciti) s.erase(x);
            izbaciti.clear();
        } else {
            cout << query(u2) - query(u1-1) << endl;
        }
    }
    return 0;
}

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