#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e5 + 5;
int n, q, k;
struct node {
int ptr;
vector<ll> versions;
node() {
ptr=0;
versions = {0};
}
node(ll val) {
ptr=0;
versions.clear();
while (val>0) {
versions.push_back(val);
val/=k;
}
versions.push_back(0);
}
void incr() {
ptr++;
}
ll get(int offset) {
int len = versions.size();
return versions[min(len-1, ptr+offset)];
}
};
ll a[maxn];
node t[4*maxn];
int mark[4*maxn];
node merge(node left, node right) {
vector<ll> versions;
for (int o=0; ; o++) {
ll L = left.get(o);
ll R = right.get(o);
versions.push_back(L+R);
if (L+R==0) break;
}
node res;
res.ptr = 0;
res.versions = versions;
return res;
}
void build(int v, int tl, int tr) {
if (tl==tr) {
t[v] = node(a[tl]);
} else {
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=merge(t[v*2],t[v*2+1]);
}
}
void push(int v) {
if (mark[v]>0) {
mark[2*v] += mark[v];
mark[2*v+1] += mark[v];
while (mark[v]>0) {
t[2*v].incr();
t[2*v+1].incr();
mark[v]--;
}
}
}
void upd(int v, int tl, int tr, int i, ll val) {
if (tl==tr) {
t[v] = node(val);
} else {
push(v);
int tm=(tl+tr)/2;
if (i<=tm) {
upd(2*v,tl,tm,i,val);
} else {
upd(2*v+1,tm+1,tr,i,val);
}
t[v]=merge(t[v*2],t[v*2+1]);
}
}
void spray(int v, int tl, int tr, int l, int r) {
if (l>r) return;
if (l==tl && tr==r) {
t[v].incr();
mark[v]++;
return;
}
push(v);
int tm=(tl+tr)/2;
spray(2*v,tl,tm,l,min(tm,r));
spray(2*v+1,tm+1,tr,max(tm+1,l),r);
t[v]=merge(t[v*2],t[v*2+1]);
}
ll qry(int v, int tl, int tr, int l, int r) {
if (l>r) return 0;
if (l==tl && tr==r) {
return t[v].get(0);
}
push(v);
int tm=(tl+tr)/2;
ll left = qry(2*v,tl,tm,l,min(tm,r));
ll right = qry(2*v+1,tm+1,tr,max(tm+1,l),r);
return left+right;
}
void setValue(int i, ll val) {
upd(1,1,n,i,val);
}
void spray(int l, int r) {
spray(1,1,n,l,r);
}
ll rangeSum(int l, int r) {
return qry(1,1,n,l,r);
}
void print() {
cout<<"tree"<<endl;
for (int i=1; i<=n; i++) {
cout<<rangeSum(i,i)<<" ";
}
cout<<endl;
for (int i=1; i<=n; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
for (int i=1; i<=9; i++) {
cout<<t[i].get(0)<<" ";
}
cout<<endl;
for (int i=1; i<=9; i++) {
cout<<mark[i]<<" ";
}
cout<<endl;
cout<<endl;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>q>>k;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
build(1,1,n);
//print();
while (q--) {
int type;
cin>>type;
if (type==1) {
int i, val;
cin>>i>>val;
setValue(i, val);
a[i]=val;
}
if (type==2) {
int l, r;
cin>>l>>r;
spray(l,r);
for (int i=l; i<=r; i++) {
a[i] /= k;
}
}
if (type==3) {
int l, r;
cin>>l>>r;
cout<<rangeSum(l,r)<<"\n";
}
//print();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
25464 KB |
Output is correct |
| 2 |
Runtime error |
787 ms |
524292 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
802 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
292 ms |
25848 KB |
Output is correct |
| 2 |
Correct |
452 ms |
26488 KB |
Output is correct |
| 3 |
Correct |
664 ms |
26744 KB |
Output is correct |
| 4 |
Correct |
1505 ms |
27000 KB |
Output is correct |
| 5 |
Execution timed out |
5066 ms |
28184 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2276 ms |
37220 KB |
Output is correct |
| 2 |
Correct |
2669 ms |
38136 KB |
Output is correct |
| 3 |
Correct |
1821 ms |
48968 KB |
Output is correct |
| 4 |
Correct |
2336 ms |
35312 KB |
Output is correct |
| 5 |
Execution timed out |
5066 ms |
49192 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
