#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"
int n, q, k;
vector<int> init;
struct segtree{
int sz = 1;
vector<array<int, 31>> sums;
array<int, 31> ID = {};
vector<int> ops;
void pull(int x){
for(int i=0; i<31; ++i) sums[x][i] = sums[2*x+1][i] + sums[2*x+2][i];
shift(sums[x], ops[x]);
}
void shift(array<int, 31> &c, int y){
for(int i=0; i<31; ++i) c[i] = (i+y) < 31 ? c[i+y] : 0;
}
void push(int x){
if(x+1<sz){
ops[2*x+1] += ops[x];
shift(sums[2*x+1], ops[x]);
ops[2*x+2] += ops[x];
shift(sums[2*x+2], ops[x]);
ops[x] = 0;
pull(x);
}
}
segtree(){
while(sz < n) sz *= 2;
sums.assign(2*sz, ID);
ops.assign(2*sz, 0);
build(0, 0, sz);
}
void build(int x, int lx, int rx){
if(rx-lx==1){
if(lx>=n) return;
for(int i=0; i<31; ++i){
sums[x][i] = init[lx]%k;
init[lx] /= k;
}
return;
}
int mx = (lx+rx)/2;
build(2*x+1, lx, mx);
build(2*x+2, mx, rx);
pull(x);
}
void divide(int l, int r, int x, int lx, int rx){
push(x);
if(r<=lx or rx<=l) return;
if(l<=lx and rx<=r){
++ops[x];
shift(sums[x], 1);
return;
}
int mx = (lx+rx)/2;
divide(l, r, 2*x+1, lx, mx);
divide(l, r, 2*x+2, mx, rx);
pull(x);
}
void divide(int l, int r){ divide(l, r+1, 0, 0, sz); }
void set(int pos, int val, int x, int lx, int rx){
push(x);
if(rx-lx==1){
for(int i=0; i<31; ++i){
sums[x][i] = val%k;
val /= k;
}
ops[x] = 0;
return;
}
int mx = (lx+rx)/2;
if(pos<mx) set(pos, val, 2*x+1, lx, mx);
else set(pos, val, 2*x+2, mx, rx);
pull(x);
}
void set(int pos, int val){ set(pos, val, 0, 0, sz); }
array<int, 31> get(int l, int r, int x, int lx, int rx){
push(x);
if(r<=lx or rx<=l) return ID;
if(l<=lx and rx<=r) return sums[x];
int mx = (lx+rx)/2;
auto resL = get(l, r, 2*x+1, lx, mx), resR = get(l, r, 2*x+2, mx, rx);
for(int i=0; i<31; ++i) resL[i] += resR[i];
return resL;
}
int get(int l, int r){
auto arr = get(l, r+1, 0, 0, sz);
int res = 0;
for(int i=0, mul=1; i<31 and mul<(int)1e11; ++i, mul*=k) res += arr[i]*mul;
return res;
}
};
signed main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q >> k;
init.resize(n);
for(int &i : init) cin >> i;
segtree st;
while(q--){
int s, t, u; cin >> s >> t >> u;
if(s==1){
st.set(t-1, u);
}else if(s==2){
st.divide(t-1, u-1);
}else{
cout << st.get(t-1, u-1) nl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
492 KB |
Output is correct |
2 |
Incorrect |
7 ms |
876 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1128 ms |
35664 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
306 ms |
4936 KB |
Output is correct |
2 |
Correct |
198 ms |
33772 KB |
Output is correct |
3 |
Correct |
295 ms |
33900 KB |
Output is correct |
4 |
Correct |
894 ms |
18296 KB |
Output is correct |
5 |
Correct |
1229 ms |
68460 KB |
Output is correct |
6 |
Correct |
1210 ms |
68332 KB |
Output is correct |
7 |
Incorrect |
1293 ms |
68428 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
899 ms |
35276 KB |
Output is correct |
2 |
Correct |
928 ms |
35692 KB |
Output is correct |
3 |
Correct |
541 ms |
34904 KB |
Output is correct |
4 |
Correct |
975 ms |
19344 KB |
Output is correct |
5 |
Correct |
1279 ms |
69620 KB |
Output is correct |
6 |
Correct |
1206 ms |
69840 KB |
Output is correct |
7 |
Correct |
1196 ms |
70008 KB |
Output is correct |
8 |
Correct |
1206 ms |
69944 KB |
Output is correct |
9 |
Correct |
1109 ms |
69656 KB |
Output is correct |
10 |
Correct |
1208 ms |
69664 KB |
Output is correct |
11 |
Correct |
1090 ms |
69392 KB |
Output is correct |
12 |
Correct |
1108 ms |
69612 KB |
Output is correct |