#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) 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:16: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:37: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:54: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:63: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Incorrect |
3 ms |
484 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
95 ms |
3520 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
3520 KB |
Output is correct |
2 |
Correct |
22 ms |
3520 KB |
Output is correct |
3 |
Correct |
33 ms |
3520 KB |
Output is correct |
4 |
Correct |
90 ms |
3520 KB |
Output is correct |
5 |
Correct |
137 ms |
6164 KB |
Output is correct |
6 |
Correct |
131 ms |
6180 KB |
Output is correct |
7 |
Incorrect |
104 ms |
6180 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
139 ms |
6180 KB |
Output is correct |
2 |
Correct |
162 ms |
6180 KB |
Output is correct |
3 |
Correct |
182 ms |
6180 KB |
Output is correct |
4 |
Correct |
183 ms |
6180 KB |
Output is correct |
5 |
Correct |
240 ms |
6348 KB |
Output is correct |
6 |
Correct |
263 ms |
6484 KB |
Output is correct |
7 |
Correct |
233 ms |
6484 KB |
Output is correct |
8 |
Correct |
327 ms |
6512 KB |
Output is correct |
9 |
Correct |
259 ms |
6512 KB |
Output is correct |
10 |
Correct |
287 ms |
6512 KB |
Output is correct |
11 |
Correct |
217 ms |
6512 KB |
Output is correct |
12 |
Correct |
378 ms |
6512 KB |
Output is correct |