// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int lim = 1 << 17;
int k;
struct segment_tree {
ll occur_drop[2 * lim][32], a[2 * lim];
int occur_prop[2 * lim];
segment_tree() {
memset(a, 0, sizeof(a));
memset(occur_drop, 0, sizeof(occur_drop));
memset(occur_prop, 0, sizeof(occur_prop));
}
void propagate(int nd, int cl, int cr) {
if(cl != cr) {
occur_prop[2 * nd] += occur_prop[nd];
occur_prop[2 * nd + 1] += occur_prop[nd];
}
//cout << occur_prop[nd] << " " << a[nd] << endl;
for(int i = 0; i < min(32, occur_prop[nd]); ++i) {
a[nd] -= occur_drop[nd][i];
occur_drop[nd][i] = 0;
}
//cout << cl << " " << cr << " " << a[nd] << endl;
for(int i = occur_prop[nd]; i < 32; ++i)
occur_drop[nd][i - occur_prop[nd]] = occur_drop[nd][i];
occur_prop[nd] = 0;
}
void upd(int nd, int cl, int cr, int idx, int val) {
propagate(nd, cl, cr);
// tambahkan occur_drop
int tmp = val, cur = 0;
a[nd] += val;
while(tmp && k != 1) {
int tmp2 = tmp / k;
occur_drop[nd][cur++] += tmp - tmp2;
tmp = tmp2;
}
//cout << cl << " " << cr << " " << a[nd] << endl;
if(cl != cr) {
int mid = (cl + cr) >> 1;
if(idx <= mid)
upd(2 * nd, cl, mid, idx, val);
else
upd(2 * nd + 1, mid + 1, cr, idx, val);
}
}
void erase(int nd, int cl, int cr, int idx, int val) {
propagate(nd, cl, cr);
// tambahkan occur_drop
int tmp = val, cur = 0;
a[nd] -= val;
while(tmp && k != 1) {
int tmp2 = tmp / k;
occur_drop[nd][cur++] -= tmp - tmp2;
tmp = tmp2;
}
//cout << cl << " " << cr << " " << a[nd] << endl;
if(cl != cr) {
int mid = (cl + cr) >> 1;
if(idx <= mid)
erase(2 * nd, cl, mid, idx, val);
else
erase(2 * nd + 1, mid + 1, cr, idx, val);
}
}
ll query(int nd, int cl, int cr, int l, int r) {
propagate(nd, cl, cr);
//cout << cl << " " << cr << " " << a[nd] << endl;
if(cl >= l && cr <= r) {
return a[nd];
}
else if(cl > r || cr < l)
return 0;
else {
int mid = (cl + cr) >> 1;
return query(2 * nd, cl, mid, l, r) + query(2 * nd + 1, mid + 1, cr, l, r);
}
}
void spray(int nd, int cl, int cr, int l, int r) {
propagate(nd, cl, cr);
if(cl >= l && cr <= r) {
++occur_prop[nd];
propagate(nd, cl, cr);
}
else if(cl > r || cr < l)
return;
else {
int mid = (cl + cr) >> 1;
spray(2 * nd, cl, mid, l, r);
spray(2 * nd + 1, mid + 1, cr, l, r);
for(int i = 0; i < 32; ++i)
occur_drop[nd][i] = occur_drop[2 * nd][i] + occur_drop[2 * nd + 1][i];
a[nd] = a[2 * nd] + a[2 * nd + 1];
}
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);
// each node maintains array of occur
// at most 30/31
int n, q;
cin >> n >> q >> k;
segment_tree seg;
for(int i = 1; i <= n; ++i) {
int x;
cin >> x;
seg.upd(1, 0, lim - 1, i, x);
}
for(;q--;) {
int s, t, u;
cin >> s >> t >> u;
if(s == 1) {
seg.erase(1, 0, lim - 1, t, seg.query(1, 0, lim - 1, t, t));
seg.upd(1, 0, lim - 1, t, u);
}
else if(s == 2) {
seg.spray(1, 0, lim - 1, t, u);
}
else {
cout << seg.query(1, 0, lim - 1, t, u) << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
69008 KB |
Output is correct |
| 2 |
Correct |
40 ms |
69068 KB |
Output is correct |
| 3 |
Correct |
38 ms |
69040 KB |
Output is correct |
| 4 |
Incorrect |
61 ms |
69028 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
69840 KB |
Output is correct |
| 2 |
Correct |
327 ms |
69644 KB |
Output is correct |
| 3 |
Correct |
299 ms |
69676 KB |
Output is correct |
| 4 |
Correct |
388 ms |
69656 KB |
Output is correct |
| 5 |
Correct |
448 ms |
69676 KB |
Output is correct |
| 6 |
Correct |
478 ms |
69736 KB |
Output is correct |
| 7 |
Correct |
457 ms |
69744 KB |
Output is correct |
| 8 |
Correct |
445 ms |
69744 KB |
Output is correct |
| 9 |
Correct |
355 ms |
69732 KB |
Output is correct |
| 10 |
Correct |
345 ms |
69732 KB |
Output is correct |
| 11 |
Correct |
359 ms |
69732 KB |
Output is correct |
| 12 |
Correct |
369 ms |
69816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
69268 KB |
Output is correct |
| 2 |
Correct |
105 ms |
69328 KB |
Output is correct |
| 3 |
Correct |
143 ms |
69408 KB |
Output is correct |
| 4 |
Correct |
316 ms |
70216 KB |
Output is correct |
| 5 |
Correct |
420 ms |
70560 KB |
Output is correct |
| 6 |
Correct |
411 ms |
70524 KB |
Output is correct |
| 7 |
Correct |
449 ms |
70636 KB |
Output is correct |
| 8 |
Correct |
429 ms |
70476 KB |
Output is correct |
| 9 |
Correct |
355 ms |
70348 KB |
Output is correct |
| 10 |
Correct |
327 ms |
70472 KB |
Output is correct |
| 11 |
Correct |
325 ms |
70356 KB |
Output is correct |
| 12 |
Correct |
338 ms |
70452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
361 ms |
69340 KB |
Output is correct |
| 2 |
Correct |
405 ms |
70912 KB |
Output is correct |
| 3 |
Incorrect |
390 ms |
70324 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
