Submission #405158

#	Time	Username	Problem	Language	Result	Execution time	Memory
405158		timmyfeng	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	248 ms	9872 KiB

sterilizing

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

struct segtree {
    segtree *left, *right;
    long long sum;

    segtree(int l, int r, int *c) {
        if (l == r) {
            sum = c[l];
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m, c);
            right = new segtree(m + 1, r, c);
            sum = left->sum + right->sum;
        }
    }

    void set(int a, int x, int l, int r) {
        if (l == r) {
            sum = x;
        } else {
            int m = (l + r) / 2;
            if (a <= m) {
                left->set(a, x, l, m);
            } else {
                right->set(a, x, m + 1, r);
            }
            sum = left->sum + right->sum;
        }
    }

    void update(int a, int b, int k, int l, int r) {
        if (b < l || r < a || k == 1 || sum == 0) {
            return;
        } else if (l == r) {
            sum /= k;
        } else {
            int m = (l + r) / 2;
            left->update(a, b, k, l, m);
            right->update(a, b, k, m + 1, r);
            sum = left->sum + right->sum;
        }
    }

    long long query(int a, int b, int l, int r) {
        if (b < l || r < a) {
            return 0;
        } else if (a <= l && r <= b) {
            return sum;
        } else {
            int m = (l + r) / 2;
            return left->query(a, b, l, m) + right->query(a, b, m + 1, r);
        }
    }
};

const int N = 100001;

int c[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
    }

    segtree *sum = new segtree(1, n, c);
    while (m--) {
        int t, x, y;
        cin >> t >> x >> y;

        if (t == 1) {
            sum->set(x, y, 1, n);
        } else if (t == 2) {
            sum->update(x, y, k, 1, n);
        } else {
            cout << sum->query(x, y, 1, n) << "\n";
        }
    }
}

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