oj.uz

Submission #879763

# Submission time Handle Problem Language Result Execution time Memory
879763 2023-11-28T05:29:10 Z Desh03 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7824 KB 
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree {
    vector<pair<long long, int>> T;
    vector<bool> lz;
    int n;
    SegmentTree(const vector<int> &v) : n(v.size()) {
        while (n & n - 1) ++n;
        T.resize(n << 1), lz.resize(n << 1);
        for (int i = 0; i < v.size(); i++) {
            T[i + n] = {v[i], v[i]};
        }
        for (int i = n - 1; i > 0; i--) {
            pull(i);
        }
    }
    void pull(int v) {
        T[v].first = T[v << 1].first + T[v << 1 | 1].first;
        T[v].second = max(T[v << 1].second, T[v << 1 | 1].second);
    }
    void push(int v) {
        T[v << 1] = T[v << 1 | 1] = {0, 0};
        lz[v << 1] = lz[v << 1 | 1] = 1;
        lz[v] = 0;
    }
    void upd0(int v, int l, int r, int u, int x) {
        if (l == r) {
            T[v] = {x, x};
            return;
        }
        if (lz[v]) push(v);
        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);
        pull(v);
    }
    void upd1(int v, int l, int r, int ql, int qr, const int &x) {
        if (l > qr || r < ql) return;
        if (l == r) {
            T[v].first /= x;
            T[v].second = T[v].first;
            return;
        }
        if (l >= ql & r <= qr && T[v].second < x) {
            T[v] = {0, 0};
            lz[v] = 1;
            return;
        }
        if (lz[v]) push(v);
        int m = l + r >> 1;
        upd1(v << 1, l, m, ql, qr, x);
        upd1(v << 1 | 1, m + 1, r, ql, qr, x);
        pull(v);
    }
    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].first;
        if (lz[v]) push(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) {
            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:10:22: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   10 |         while (n & n - 1) ++n;
      |                    ~~^~~
sterilizing.cpp:12:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
sterilizing.cpp: In member function 'void SegmentTree::upd0(int, int, int, int, int)':
sterilizing.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int m = l + r >> 1;
      |                 ~~^~~
sterilizing.cpp: In member function 'void SegmentTree::upd1(int, int, int, int, int, const int&)':
sterilizing.cpp:46:15: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   46 |         if (l >= ql & r <= qr && T[v].second < x) {
      |             ~~^~~~~
sterilizing.cpp:52:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int m = l + r >> 1;
      |                 ~~^~~
sterilizing.cpp: In member function 'long long int SegmentTree::qry(int, int, int, int, int)':
sterilizing.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 5 ms 680 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 468 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 680 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4778 ms 5188 KB Output is correct
2 Correct 2967 ms 4968 KB Output is correct
3 Correct 4760 ms 6836 KB Output is correct
4 Execution timed out 5041 ms 7184 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1116 KB Output is correct
2 Correct 11 ms 2908 KB Output is correct
3 Correct 16 ms 2908 KB Output is correct
4 Correct 51 ms 3004 KB Output is correct
5 Correct 57 ms 6224 KB Output is correct
6 Correct 58 ms 6468 KB Output is correct
7 Execution timed out 5101 ms 6072 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4344 KB Output is correct
2 Correct 81 ms 4432 KB Output is correct
3 Correct 89 ms 3924 KB Output is correct
4 Correct 105 ms 3392 KB Output is correct
5 Correct 117 ms 7628 KB Output is correct
6 Correct 129 ms 7504 KB Output is correct
7 Correct 110 ms 7484 KB Output is correct
8 Correct 158 ms 7600 KB Output is correct
9 Correct 146 ms 7824 KB Output is correct
10 Correct 157 ms 7508 KB Output is correct
11 Correct 121 ms 7536 KB Output is correct
12 Correct 212 ms 7760 KB Output is correct