#include<bits/stdc++.h>
using namespace std;
int n, q, k;
void build (int l, int r, long long int* segtree, int pos) {
if (l == r) {
//takes input in the order 1...n
cin >> segtree[pos];
return;
}
int mid = (l + r)/2;
build (l, mid, segtree, pos * 2);
build (mid + 1, r, segtree, pos * 2 + 1);
segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
}
int query (int l, int r, int target_l, int target_r, long long int* segtree, int pos) {
// no intersection
if (r < target_l || l > target_r) {
return 0;
} if (target_l <= l && r <= target_r) { //total intersection
#ifdef DEBUG
printf ("Total intersection querying range (%d, %d): %lld\n", l, r, segtree[pos]);
#endif
return segtree[pos];
} else { //partial intersection
int mid = (l + r)/2;
return query(l, mid, target_l, target_r, segtree, pos*2) +
query(mid + 1, r, target_l, target_r, segtree, pos*2 + 1);
}
}
void spray (int l, int r, int target_l, int target_r, long long int* segtree, int pos) {
// no intersection
if (r < target_l || l > target_r) {return;}
if (target_l <= l && r <= target_r && l == r) {
#ifdef DEBUG
printf ("Sprayed %dth dish: was %lld, now is %lld\n", l, segtree[pos], segtree[pos] / k);
#endif
segtree[pos] = segtree[pos] / k;
return;
}
//micro-optimization: don't need to visit further subnodes, mark whole subtree as zero and move on
if (target_l <= l && r <= target_r && segtree[pos] < k) {
segtree[pos] = 0;
return;
}
int mid = (l + r)/2;
spray (l, mid, target_l, target_r, segtree, pos * 2);
spray (mid + 1, r, target_l, target_r, segtree, pos * 2 + 1);
#ifdef DEBUG
printf ("Updating range (%d, %d) to %lld (from %lld)\n", l, r, segtree[pos * 2] + segtree[pos * 2 + 1], segtree[pos]);
#endif
segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
}
void update (int l, int r, long long int* segtree, int pos, int index, int value) {
if (l == r) {
segtree[pos] = value;
return;
}
int mid = (l + r)/2;
if (index <= mid) {
update (l, mid, segtree, pos * 2, index, value);
} else {
update (mid + 1, r, segtree, pos * 2 + 1, index, value);
}
segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
}
#ifdef DEBUG
void view_arr (int l, int r, long long int* segtree, int pos) {
if (l == r) {
printf ("%02lld ", segtree[pos]);
return;
}
int mid = (l + r)/2;
view_arr (l, mid, segtree, pos * 2);
view_arr (mid + 1, r, segtree, pos * 2 + 1);
}
#endif
// we can't use a range-update range-query segtree as is because
// integer division is not distributive
// i.e. 2//3 + 1//3 != 3//3
// thus we can't apply division to sum of dishes directly
// we'll have to update all dishes individually
int main () {
cin >> n >> q >> k;
long long int segtree[4*n + 1];
build (1, n, segtree, 1);
for (int i = 0; i < q; i++) {
int op_type; cin >> op_type;
if (op_type == 1) {
int ind, val; cin >> ind >> val;
#ifdef DEBUG
printf ("Setting %d dish to %d\n", ind, val);
#endif
update (1, n, segtree, 1, ind, val);
} else if (op_type == 2) {
int l, r; cin >> l >> r;
#ifdef DEBUG
printf ("Spraying %d to %d dishes\n", l, r);
#endif
spray (1, n, l, r, segtree, 1);
} else if (op_type == 3) {
int l, r; cin >> l >> r;
#ifdef DEBUG
printf ("Querying amount in %d to %d dishes\n", l, r);
#endif
cout << query(1, n, l, r, segtree, 1) << endl;
}
#ifdef DEBUG
view_arr (1, n, segtree, 1);
cout << endl;
#endif
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4546 ms |
3980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
3524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
