#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 1e5 + 10;
ll t[maxn << 2], mx[maxn << 2];
int a[maxn], lazy[maxn << 2], n, q, k;
void build(int node, int l, int r) {
if(l == r) {
t[node] = a[l];
mx[node] = a[l];
return;
} int m = l + r >> 1;
build(node << 1, l, m);
build(node << 1 | 1, m + 1, r);
t[node] = t[node << 1] + t[node << 1 | 1];
mx[node] = max(mx[node << 1], mx[node << 1 | 1]);
}
void shift(int node) {
if(!lazy[node]) return;
t[node << 1] = mx[node << 1] = 0;
t[node << 1 | 1] = mx[node << 1 | 1] = 0;
lazy[node << 1] = lazy[node << 1 | 1] = 1;
lazy[node] = 0;
}
void change(int node, int l, int r, int i, int x) {
if(r < i || l > i) return;
if(l == r) {
t[node] = mx[node] = x;
return;
} shift(node);
int m = l + r >> 1;
if(i <= m) change(node << 1, l, m, i, x);
else change(node << 1 | 1, m + 1, r, i, x);
t[node] = t[node << 1] + t[node << 1 | 1];
mx[node] = max(mx[node << 1], mx[node << 1 | 1]);
}
void update(int node, int l, int r, int i, int j) {
if(r < i || l > j || mx[node] == 0) return;
if(i <= l && r <= j && mx[node] < k) {
t[node] = mx[node] = 0;
lazy[node] = 1; return;
}
if(l == r) {
t[node] = mx[node] = t[node] / k;
return;
} shift(node);
int m = l + r >> 1;
update(node << 1, l, m, i, j);
update(node << 1 | 1, m + 1, r, i, j);
t[node] = t[node << 1] + t[node << 1 | 1];
mx[node] = max(mx[node << 1], mx[node << 1 | 1]);
}
ll query(int node, int l, int r, int i, int j) {
if(r < i || l > j) return 0;
if(i <= l && r <= j) return t[node];
shift(node); int m = l + r >> 1;
return query(node << 1, l, m, i, j) +
query(node << 1 | 1, m + 1, r, i, j);
}
int main(int argc, char const *argv[]) {
scanf("%d %d %d", &n, &q, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
while(q--) {
int t, l, r;
scanf("%d %d %d", &t, &l, &r);
if(t == 1) change(1, 1, n, l, r);
else if(t == 2 && k != 1) update(1, 1, n, l, r);
else printf("%lld\n", query(1, 1, n, l, r));
}
}
Compilation message
sterilizing.cpp: In function 'void build(int, int, int)':
sterilizing.cpp:19:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
} int m = l + r >> 1;
~~^~~
sterilizing.cpp: In function 'void change(int, int, int, int, int)':
sterilizing.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
sterilizing.cpp: In function 'void update(int, int, int, int, int)':
sterilizing.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
sterilizing.cpp: In function 'll query(int, int, int, int, int)':
sterilizing.cpp:66:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
shift(node); int m = l + r >> 1;
~~^~~
sterilizing.cpp: In function 'int main(int, const char**)':
sterilizing.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &q, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
sterilizing.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &t, &l, &r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
3648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
3648 KB |
Output is correct |
| 2 |
Correct |
19 ms |
3648 KB |
Output is correct |
| 3 |
Correct |
26 ms |
3648 KB |
Output is correct |
| 4 |
Correct |
71 ms |
3648 KB |
Output is correct |
| 5 |
Correct |
98 ms |
6268 KB |
Output is correct |
| 6 |
Correct |
94 ms |
6268 KB |
Output is correct |
| 7 |
Incorrect |
102 ms |
6268 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
6268 KB |
Output is correct |
| 2 |
Correct |
133 ms |
6268 KB |
Output is correct |
| 3 |
Correct |
150 ms |
6268 KB |
Output is correct |
| 4 |
Correct |
161 ms |
6268 KB |
Output is correct |
| 5 |
Correct |
218 ms |
6444 KB |
Output is correct |
| 6 |
Correct |
232 ms |
6572 KB |
Output is correct |
| 7 |
Correct |
203 ms |
6572 KB |
Output is correct |
| 8 |
Correct |
271 ms |
6692 KB |
Output is correct |
| 9 |
Correct |
235 ms |
6692 KB |
Output is correct |
| 10 |
Correct |
244 ms |
6692 KB |
Output is correct |
| 11 |
Correct |
183 ms |
6692 KB |
Output is correct |
| 12 |
Correct |
315 ms |
6692 KB |
Output is correct |
