Submission #960027

#	Time	Username	Problem	Language	Result	Execution time	Memory
960027		Blagoj	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	168 ms	8532 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

int n, q, K;
vector<int> v;

struct SegmentTree {
    vector<ll> sum, mx;

    SegmentTree(int mxn) {
        sum.resize(3 * mxn);
        mx.resize(3 * mxn);
    }

    void pull(int k) {
        mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
        sum[k] = sum[k * 2] + sum[k * 2 + 1];
    }

    void build(int k, int l, int r) {
        if (l == r) {
            sum[k] = mx[k] = v[l];
            return;
        }
        int mid = (l + r) / 2;
        build(k * 2, l, mid);
        build(k * 2 + 1, mid + 1, r);
        pull(k);
    }

    void update1(int k, int l, int r, int i, ll v) {
        if (l > i || r < i) return;
        if (l == r) {
            sum[k] = mx[k] = v;
            return;
        }
        int mid = (l + r) / 2;
        update1(k * 2, l, mid, i, v);
        update1(k * 2 + 1, mid + 1, r, i, v);
        pull(k);
    }

    void update2(int k, int l, int r, int i, int j) {
        if (l > j || r < i || mx[k] == 0) return;
        if (l == r) {
            sum[k] = mx[k] = sum[k] / K;
            return;
        }
        int mid = (l + r) / 2;
        update2(k * 2, l, mid, i, j);
        update2(k * 2 + 1, mid + 1, r, i, j);
        pull(k);
    }

    ll get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return 0;
        if (i <= l && r <= j) return sum[k];
        int mid = (l + r) / 2;
        return get(k * 2, l, mid, i, j) + get(k * 2 + 1, mid + 1, r, i, j);
    }
} sgt(1e5 + 10); 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q >> K;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    sgt.build(1, 1, n);
    while (q--) {
        ll t, l, r;
        cin >> t >> l >> r;
        if (t == 1) sgt.update1(1, 1, n, l, r);
        if (t == 2 && K != 1) sgt.update2(1, 1, n, l, r);
        if (t == 3) cout << sgt.get(1, 1, n, l, r) << endl;
    }
}

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