// 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_drop[nd][i] = 0;
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 |
Incorrect |
42 ms |
69068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
398 ms |
69808 KB |
Output is correct |
| 2 |
Correct |
358 ms |
69720 KB |
Output is correct |
| 3 |
Correct |
301 ms |
69520 KB |
Output is correct |
| 4 |
Correct |
386 ms |
69580 KB |
Output is correct |
| 5 |
Correct |
523 ms |
69680 KB |
Output is correct |
| 6 |
Correct |
462 ms |
69780 KB |
Output is correct |
| 7 |
Correct |
490 ms |
69696 KB |
Output is correct |
| 8 |
Correct |
461 ms |
69744 KB |
Output is correct |
| 9 |
Correct |
391 ms |
69676 KB |
Output is correct |
| 10 |
Correct |
386 ms |
69840 KB |
Output is correct |
| 11 |
Correct |
394 ms |
69908 KB |
Output is correct |
| 12 |
Correct |
400 ms |
69708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
69344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
372 ms |
69552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
