Submission #1187773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187773		peteza	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	137 ms	3912 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, k, a, b, c;
int segmax[800005];
ll segsum[800005];

void updpnt(int idx, int l, int r, int tgt, int val) {
    if(l == r) {
        segsum[idx] = segmax[idx] = val;
        return ;
    }
    int mid = (l+r) >> 1;
    if(tgt <= mid) updpnt(idx*2+1, l, mid, tgt, val);
    else updpnt(idx*2+2, mid+1, r, tgt, val);
    segsum[idx] = segsum[idx*2+1] + segsum[idx*2+2];
    segmax[idx] = max(segmax[idx*2+1], segmax[idx*2+2]);
}

void updrng(int idx, int l, int r, int tl, int tr) {
    if(tr < l || r < tl) return ;
    if(!segmax[idx]) return;
    if(l == r) {
        segsum[idx] /= k;
        segmax[idx] = segsum[idx];
        return ;
    }
    int mid = (l+r) >> 1;
    updrng(idx*2+1, l, mid, tl, tr); updrng(idx*2+2, mid+1, r, tl, tr);
    segsum[idx] = segsum[idx*2+1] + segsum[idx*2+2];
    segmax[idx] = max(segmax[idx*2+1], segmax[idx*2+2]);
}

ll qr(int idx, int l, int r, int tl, int tr) {
    if(tr < l || r < tl) return 0;
    if(tl <= l && r <= tr) return segsum[idx];
    int mid = (l+r) >> 1;
    return qr(idx*2+1, l, mid, tl, tr) + qr(idx*2+2, mid+1, r, tl, tr);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q >> k;
    for(int i=1;i<=n;i++) {
        cin >> a;
        updpnt(0, 1, n, i, a);
    }
    while(q--) {
        cin >> a >> b >> c;
        if(a == 1) {
            updpnt(0, 1, n, b, c);
        } else if(a == 2) {
            if(k != 1) updrng(0, 1, n, b, c);
        } else {
            cout << qr(0, 1, n, b, c) << '\n';
        }
    }
}

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