oj.uz

Submission #879765

# Submission time Handle Problem Language Result Execution time Memory
879765 2023-11-28T05:38:03 Z Desh03 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 122 ms 3408 KB 
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree {
    vector<long long> T;
    int n;
    SegmentTree(const vector<int> &v) : n(v.size()) {
        while (n & n - 1) ++n;
        T.resize(n << 1);
        for (int i = 0; i < v.size(); i++) {
            T[i + n] = v[i];
        }
        for (int i = n - 1; i > 0; i--) {
            T[i] = T[i << 1] + T[i << 1 | 1];
        }
    }
    void upd0(int v, int l, int r, int u, int x) {
        if (l == r) {
            T[v] = x;
            return;
        }
        int m = l + r >> 1;
        if (u <= m) upd0(v << 1, l, m, u, x);
        else upd0(v << 1 | 1, m + 1, r, u, x);
        T[v] = T[v << 1] + T[v << 1 | 1];
    }
    void upd1(int v, int l, int r, int ql, int qr, const int &x) {
        if (l > qr || r < ql || !T[v]) return;
        if (l == r) {
            T[v] /= x;
            return;
        }
        int m = l + r >> 1;
        upd1(v << 1, l, m, ql, qr, x);
        upd1(v << 1 | 1, m + 1, r, ql, qr, x);
        T[v] = T[v << 1] + T[v << 1 | 1];
    }
    long long qry(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return T[v];
        int m = l + r >> 1;
        return qry(v << 1, l, m, ql, qr) + qry(v << 1 | 1, m + 1, r, ql, qr);
    }
    void upd0(int u, int x) {
        upd0(1, 0, n - 1, u, x);
    }
    void upd1(int l, int r, const int &x) {
        upd1(1, 0, n - 1, l, r, x);
    }
    long long qry(int l, int r) {
        return qry(1, 0, n - 1, l, r);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q, k;
    cin >> n >> q >> k;
    vector<int> v(n);
    for (int &x : v) {
        cin >> x;
    }
    SegmentTree st(v);
    while (q--) {
        int s, t, u;
        cin >> s >> t >> u;
        if (s == 1) {
            st.upd0(--t, u);
        } else if (s == 2) {
            if (k > 1) st.upd1(--t, --u, k);
        } else {
            cout << st.qry(--t, --u) << '\n';
        }
    }
    return 0;
}

Compilation message

sterilizing.cpp: In constructor 'SegmentTree::SegmentTree(const std::vector<int>&)':
sterilizing.cpp:9:22: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
    9 |         while (n & n - 1) ++n;
      |                    ~~^~~
sterilizing.cpp:11:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
sterilizing.cpp: In member function 'void SegmentTree::upd0(int, int, int, int, int)':
sterilizing.cpp:23:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int m = l + r >> 1;
      |                 ~~^~~
sterilizing.cpp: In member function 'void SegmentTree::upd1(int, int, int, int, int, const int&)':
sterilizing.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int m = l + r >> 1;
      |                 ~~^~~
sterilizing.cpp: In member function 'long long int SegmentTree::qry(int, int, int, int, int)':
sterilizing.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1884 KB Output is correct
2 Correct 30 ms 1884 KB Output is correct
3 Correct 31 ms 2904 KB Output is correct
4 Correct 33 ms 3160 KB Output is correct
5 Correct 40 ms 3280 KB Output is correct
6 Correct 40 ms 3156 KB Output is correct
7 Correct 40 ms 3356 KB Output is correct
8 Correct 44 ms 3156 KB Output is correct
9 Correct 43 ms 3376 KB Output is correct
10 Correct 36 ms 3320 KB Output is correct
11 Correct 37 ms 3164 KB Output is correct
12 Correct 38 ms 3152 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 604 KB Output is correct
2 Correct 9 ms 1624 KB Output is correct
3 Correct 11 ms 1624 KB Output is correct
4 Correct 32 ms 1108 KB Output is correct
5 Correct 39 ms 2920 KB Output is correct
6 Correct 39 ms 2928 KB Output is correct
7 Correct 35 ms 2976 KB Output is correct
8 Correct 39 ms 2908 KB Output is correct
9 Correct 35 ms 2940 KB Output is correct
10 Correct 35 ms 2948 KB Output is correct
11 Correct 37 ms 2908 KB Output is correct
12 Correct 37 ms 2908 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1720 KB Output is correct
2 Correct 54 ms 1836 KB Output is correct
3 Correct 54 ms 1624 KB Output is correct
4 Correct 65 ms 1364 KB Output is correct
5 Correct 76 ms 2928 KB Output is correct
6 Correct 86 ms 2992 KB Output is correct
7 Correct 82 ms 3156 KB Output is correct
8 Correct 97 ms 3068 KB Output is correct
9 Correct 88 ms 3408 KB Output is correct
10 Correct 96 ms 3212 KB Output is correct
11 Correct 74 ms 3156 KB Output is correct
12 Correct 122 ms 3188 KB Output is correct