oj.uz

Submission #973804

# Submission time Handle Problem Language Result Execution time Memory
973804 2024-05-02T11:10:38 Z VMaksimoski008 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 10280 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() {
    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) tree.spray(l-1, r-1);
        else cout << tree.query(l-1, r-1) << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5009 ms 5712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1372 KB Output is correct
2 Correct 23 ms 4184 KB Output is correct
3 Correct 34 ms 4012 KB Output is correct
4 Correct 110 ms 3412 KB Output is correct
5 Correct 122 ms 8772 KB Output is correct
6 Correct 132 ms 8900 KB Output is correct
7 Execution timed out 5060 ms 8732 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 6276 KB Output is correct
2 Correct 135 ms 5948 KB Output is correct
3 Correct 125 ms 4736 KB Output is correct
4 Correct 158 ms 4688 KB Output is correct
5 Correct 203 ms 10188 KB Output is correct
6 Correct 201 ms 10184 KB Output is correct
7 Correct 192 ms 10188 KB Output is correct
8 Correct 232 ms 10280 KB Output is correct
9 Correct 211 ms 9928 KB Output is correct
10 Correct 226 ms 9932 KB Output is correct
11 Correct 191 ms 9888 KB Output is correct
12 Correct 270 ms 9932 KB Output is correct