제출 #405157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405157		timmyfeng	Sterilizing Spray (JOI15_sterilizing)	C++17	10 / 100	88 ms	8484 KiB

sterilizing

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

struct segtree {
    segtree *left, *right;
    int 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;
        }
    }

    int 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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75