#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) {
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: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;
| ~~^~~
| # |
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 |
612 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 |
604 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 |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
3160 KB |
Output is correct |
| 2 |
Correct |
33 ms |
2972 KB |
Output is correct |
| 3 |
Correct |
36 ms |
5712 KB |
Output is correct |
| 4 |
Correct |
36 ms |
5456 KB |
Output is correct |
| 5 |
Correct |
43 ms |
7764 KB |
Output is correct |
| 6 |
Correct |
43 ms |
7760 KB |
Output is correct |
| 7 |
Correct |
49 ms |
7760 KB |
Output is correct |
| 8 |
Correct |
50 ms |
8080 KB |
Output is correct |
| 9 |
Correct |
40 ms |
7768 KB |
Output is correct |
| 10 |
Correct |
41 ms |
7672 KB |
Output is correct |
| 11 |
Correct |
40 ms |
7760 KB |
Output is correct |
| 12 |
Correct |
40 ms |
7756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
604 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
16 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
47 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
58 ms |
5044 KB |
Output is correct |
| 6 |
Correct |
63 ms |
5208 KB |
Output is correct |
| 7 |
Correct |
39 ms |
5372 KB |
Output is correct |
| 8 |
Correct |
58 ms |
6424 KB |
Output is correct |
| 9 |
Correct |
53 ms |
6228 KB |
Output is correct |
| 10 |
Correct |
51 ms |
6156 KB |
Output is correct |
| 11 |
Correct |
51 ms |
6144 KB |
Output is correct |
| 12 |
Correct |
52 ms |
6164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
2900 KB |
Output is correct |
| 2 |
Correct |
81 ms |
2896 KB |
Output is correct |
| 3 |
Correct |
89 ms |
2716 KB |
Output is correct |
| 4 |
Correct |
107 ms |
1876 KB |
Output is correct |
| 5 |
Correct |
114 ms |
5204 KB |
Output is correct |
| 6 |
Correct |
130 ms |
5204 KB |
Output is correct |
| 7 |
Correct |
114 ms |
5208 KB |
Output is correct |
| 8 |
Correct |
161 ms |
5204 KB |
Output is correct |
| 9 |
Correct |
140 ms |
5204 KB |
Output is correct |
| 10 |
Correct |
159 ms |
5200 KB |
Output is correct |
| 11 |
Correct |
118 ms |
5200 KB |
Output is correct |
| 12 |
Correct |
210 ms |
5204 KB |
Output is correct |
