#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int K, C;
struct segtree{
struct node{
ll divisions;
deque<ll> d;
node(){
divisions = 0;
d.assign(C, 0);
}
node(ll x){
divisions = 0;
d.assign(C, 0);
for(int i = 0; i < C; i++){
d[i] = x%K;
x/=K;
}
reverse(d.begin(), d.end());
}
node operator+(node a){
node rt;
for(int i = 0; i < C; i++) rt.d[i] = d[i]+a.d[i];
return rt;
}
void pushdown_from(node p){
int x = p.divisions;
if(x >= C) d.assign(C, 0);
else{
while(x--) d.pop_back(), d.push_front(0);
}
}
};
int k;
vector<node> v;
segtree(int n){
k = 1;
while(k < n) k*=2; k*=2;
v.assign(k, node());
}
void update(int in, int nd, int a, int b, ll x){
if(a == b){
v[nd] = node(x);
return;
}
int md = (a+b)/2;
v[2*nd].pushdown_from(v[nd]);
v[2*nd+1].pushdown_from(v[nd]);
v[nd].divisions = 0;
if(in <= md) update(in, 2*nd, a, md, x);
else update(in, 2*nd+1, md+1, b, x);
v[nd] = v[2*nd]+v[2*nd+1];
}
void update(int in, ll x){
update(in, 1, 0, k/2-1, x);
}
void spray(int l, int r, int nd, int a, int b){
if(a > r || b < l) return;
if(a >= l && b <= r){
v[nd].d.pop_back();
v[nd].d.push_front(0);
v[nd].divisions++;
return;
}
int md = (a+b)/2;
v[2*nd].pushdown_from(v[nd]);
v[2*nd+1].pushdown_from(v[nd]);
v[nd].divisions = 0;
spray(l, r, 2*nd, a, md);
spray(l, r, 2*nd+1, md+1, b);
v[nd] = v[2*nd]+v[2*nd+1];
}
void spray(int l, int r){
spray(l, r, 1, 0, k/2-1);
}
ll sum(int l, int r, int nd, int a, int b){
if(a > r || b < l) return 0;
if(a >= l && b <= r){
ll p = 1, s = 0;
for(int i = C-1; i >= 0; i--) s+=v[nd].d[i]*p, p*=K;
return s;
}
int md = (a+b)/2;
v[2*nd].pushdown_from(v[nd]);
v[2*nd+1].pushdown_from(v[nd]);
v[nd].divisions = 0;
ll rt = sum(l, r, 2*nd, a, md) + sum(l, r, 2*nd+1, md+1, b);
v[nd] = v[2*nd]+v[2*nd+1];
return rt;
}
ll sum(int l, int r){
return sum(l, r, 1, 0, k/2-1);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q >> K;
ll p = 1; C = 0;
while(p < ll(1e9)) p*=K, C++;
segtree seg(n);
for(int i = 0; i < n; i++){
ll x; cin >> x;
seg.update(i, x);
}
while(q--){
int tt; cin >> tt;
if(tt == 1){
int in; ll x; cin >> in >> x; in--;
seg.update(in, x);
}
if(tt == 2){
int l, r; cin >> l >> r; l--, r--;
seg.spray(l, r);
}
if(tt == 3){
int l, r; cin >> l >> r; l--, r--;
cout << seg.sum(l, r) << "\n";
}
}
}
Compilation message
sterilizing.cpp: In constructor 'segtree::segtree(int)':
sterilizing.cpp:47:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
47 | while(k < n) k*=2; k*=2;
| ^~~~~
sterilizing.cpp:47:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
47 | while(k < n) k*=2; k*=2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5051 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
473 ms |
18716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1620 ms |
144764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
