Submission #601364

#	Time	Username	Problem	Language	Result	Execution time	Memory
601364		elkernos	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	211 ms	7712 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

struct T {
    long long sum = 0;
    int mark = 0;
    void init(int x)
    {
        sum = x;
        mark = (x == 0);
    }
    void merge(T a, T b)
    {
        sum = a.sum + b.sum;
        mark = a.mark & b.mark;
    }
};

T tr[1 << 18];
int a[1 << 18];
int k;
#define lc 2 * v
#define rc 2 * v + 1
#define m (l + r) / 2

void init(int v, int l, int r)
{
    if(l == r) {
        tr[v].init(a[l]);
        return;
    }
    init(lc, l, m), init(rc, m + 1, r);
    tr[v].merge(tr[lc], tr[rc]);
}
void point(int v, int l, int r, int pos, int val)
{
    if(l == r) {
        tr[v].init(val);
        return;
    }
    if(pos <= m) {
        point(lc, l, m, pos, val);
    }
    else {
        point(rc, m + 1, r, pos, val);
    }
    tr[v].merge(tr[lc], tr[rc]);
}
void range(int v, int l, int r, int ql, int qr)
{
    if(r < ql || qr < l || tr[v].mark) {
        return;
    }
    if(l == r) {
        tr[v].init(tr[v].sum / k);
        return;
    }
    range(lc, l, m, ql, qr), range(rc, m + 1, r, ql, qr);
    tr[v].merge(tr[lc], tr[rc]);
}
long long sum(int v, int l, int r, int ql, int qr)
{
    if(r < ql || qr < l) {
        return 0;
    }
    if(ql <= l && r <= qr) {
        return tr[v].sum;
    }
    return sum(lc, l, m, ql, qr) + sum(rc, m + 1, r, ql, qr);
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    init(1, 1, n);
    for(int i = 1; i <= q; ++i) {
        int t;
        cin >> t;
        if(t == 1) {
            int a, b;
            cin >> a >> b;
            point(1, 1, n, a, b);
        }
        else if(t == 2) {
            int a, b;
            cin >> a >> b;
            if(k > 1) {
                range(1, 1, n, a, b);
            }
        }
        else if(t == 3) {
            int a, b;
            cin >> a >> b;
            cout << sum(1, 1, n, a, b) << '\n';
        }
    }
}

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