#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[]) {
#ifdef LOCAL_TESTING
freopen("in", "r", stdin);
#endif
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:74: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:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
sterilizing.cpp:80: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 |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
4312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
4312 KB |
Output is correct |
| 2 |
Correct |
18 ms |
4312 KB |
Output is correct |
| 3 |
Correct |
26 ms |
4312 KB |
Output is correct |
| 4 |
Correct |
74 ms |
4312 KB |
Output is correct |
| 5 |
Correct |
106 ms |
6764 KB |
Output is correct |
| 6 |
Correct |
109 ms |
6772 KB |
Output is correct |
| 7 |
Incorrect |
110 ms |
6772 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
6772 KB |
Output is correct |
| 2 |
Correct |
134 ms |
6772 KB |
Output is correct |
| 3 |
Correct |
151 ms |
6772 KB |
Output is correct |
| 4 |
Correct |
167 ms |
6772 KB |
Output is correct |
| 5 |
Correct |
197 ms |
7540 KB |
Output is correct |
| 6 |
Correct |
231 ms |
7632 KB |
Output is correct |
| 7 |
Correct |
188 ms |
7632 KB |
Output is correct |
| 8 |
Correct |
322 ms |
7684 KB |
Output is correct |
| 9 |
Correct |
208 ms |
7684 KB |
Output is correct |
| 10 |
Correct |
238 ms |
7684 KB |
Output is correct |
| 11 |
Correct |
181 ms |
7684 KB |
Output is correct |
| 12 |
Correct |
314 ms |
7684 KB |
Output is correct |
