oj.uz

Submission #973806

# Submission time Handle Problem Language Result Execution time Memory
973806 2024-05-02T11:11:54 Z VMaksimoski008 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 186 ms 10460 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SegTree {
    int n, k;
    vector<int> v;
    vector<ll> sum, mx;

    SegTree(vector<int> _v, int _k) {
        n = _v.size();
        v = _v;
        k = _k;
        sum.resize(4*n+5);
        mx.resize(4*n+5);
        build(1, 0, n-1);
    }

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

    void build(int u, int tl, int tr) {
        if(tl == tr) {
            sum[u] = mx[u] = v[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            merge(u);
        }
    }

    void set(int u, int tl, int tr, int p, int v) {
        if(tl == tr) {
            sum[u] = mx[u] = v;
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) set(2*u, tl, tm, p, v);
            else set(2*u+1, tm+1, tr, p, v);
            merge(u);
        }
    }

    void spray(int u, int tl, int tr, int l, int r) {
        if(tl > tr || l > tr || tl > r || !mx[u]) return ;

        if(tl == tr) {
            sum[u] /= k;
            mx[u] /= k;
            return ;
        }

        int tm = (tl + tr) / 2;
        spray(2*u, tl, tm, l, r);
        spray(2*u+1, tm+1, tr, l, r);
        merge(u);
    }

    ll query(int u, int tl, int tr, int l, int r) {
        if(tl > tr || l > tr || tl > r) return 0;
        if(l <= tl && tr <= r) return sum[u];
        int tm = (tl + tr) / 2;
        return query(2*u, tl, tm, l, r)
        + query(2*u+1, tm+1, tr, l, r);
    }

    ll query(int l, int r) { return query(1, 0, n-1, l, r); }
    void set(int p, int v) { set(1, 0, n-1, p, v); }
    void spray(int l, int r) { spray(1, 0, n-1, l, r); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    
    int n, q, k, t, l, r;
    cin >> n >> q >> k;

    vector<int> v(n);
    for(int &x : v) cin >> x;

    SegTree tree(v, k);

    while(q--) {
        cin >> t >> l >> r;

        if(t == 1) tree.set(l-1, r);
        else if(t == 2 && k > 1) tree.spray(l-1, r-1);
        else if(t == 3) cout << tree.query(l-1, r-1) << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 684 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4496 KB Output is correct
2 Correct 33 ms 4824 KB Output is correct
3 Correct 30 ms 7716 KB Output is correct
4 Correct 42 ms 9912 KB Output is correct
5 Correct 46 ms 10440 KB Output is correct
6 Correct 45 ms 10184 KB Output is correct
7 Correct 52 ms 10460 KB Output is correct
8 Correct 45 ms 10440 KB Output is correct
9 Correct 45 ms 10120 KB Output is correct
10 Correct 42 ms 10192 KB Output is correct
11 Correct 41 ms 10188 KB Output is correct
12 Correct 43 ms 10436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 856 KB Output is correct
2 Correct 9 ms 3676 KB Output is correct
3 Correct 13 ms 3676 KB Output is correct
4 Correct 34 ms 2136 KB Output is correct
5 Correct 49 ms 7772 KB Output is correct
6 Correct 46 ms 7772 KB Output is correct
7 Correct 39 ms 7772 KB Output is correct
8 Correct 46 ms 8944 KB Output is correct
9 Correct 40 ms 8648 KB Output is correct
10 Correct 41 ms 8652 KB Output is correct
11 Correct 41 ms 8680 KB Output is correct
12 Correct 41 ms 8660 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4188 KB Output is correct
2 Correct 65 ms 4268 KB Output is correct
3 Correct 76 ms 3676 KB Output is correct
4 Correct 88 ms 2932 KB Output is correct
5 Correct 99 ms 7880 KB Output is correct
6 Correct 106 ms 7772 KB Output is correct
7 Correct 90 ms 7772 KB Output is correct
8 Correct 130 ms 7772 KB Output is correct
9 Correct 123 ms 7772 KB Output is correct
10 Correct 132 ms 7772 KB Output is correct
11 Correct 99 ms 7820 KB Output is correct
12 Correct 186 ms 7768 KB Output is correct