제출 #521766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521766		tengiz05	Sterilizing Spray (JOI15_sterilizing)	C++17	0 / 100	5089 ms	5376 KiB

sterilizing

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 100005;
int n, k;
struct Info {
    int mx;
    int sum;
    Info(int x = 0) : mx(x), sum(x) {}
};
Info operator+(const Info &a, const Info &b) {
    Info res;
    res.mx = std::max(a.mx, b.mx);
    res.sum = a.sum + b.sum;
    return res;
}
Info t[4 * N];
void modify(int p, int l, int r, int x, int y) {
    if (l == r - 1) {
        t[p] = Info(y);
        return;
    }
    int m = (l + r) / 2;
    if (x < m) {
        modify(2 * p, l, m, x, y);
    } else {
        modify(2 * p + 1, m, r, x, y);
    }
    t[p] = t[2 * p] + t[2 * p + 1];
}
void apply(int p, int l, int r, int x, int y) {
    if (r <= x || y <= l || t[p].mx == 0) {
        return;
    }
    if (l == r - 1) {
        t[p] = Info(t[p].mx / k);
        return;
    }
    int m = (l + r) / 2;
    apply(2 * p, l, m, x, y);
    apply(2 * p + 1, m, r, x, y);
    t[p] = t[2 * p] + t[2 * p + 1];
}
Info query(int p, int l, int r, int x, int y) {
    if (r <= x || y <= l) {
        return Info();
    }
    if (x <= l && r <= y) {
        return t[p];
    }
    int m = (l + r) / 2;
    return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int q;
    std::cin >> n >> q >> k;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        modify(1, 0, n, i, a[i]);
    }
    
    while (q--) {
        int op, x, y;
        std::cin >> op >> x >> y;
        
        x--;
        
        if (op == 1) {
            modify(1, 0, n, x, y);
        } else if (op == 2) {
            apply(1, 0, n, x, y);
        } else {
            std::cout << query(1, 0, n, x, y).sum << "\n";
        }
    }
    
    return 0;
}

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