#include <bits/stdc++.h>
using namespace std;
int n,q,k,x,y;
long long a[100007],it[400007],mx[400007],lazy[400007];
void init(int p,int l,int r){
if(l==r){
it[p]=a[l];
mx[p]=a[l];
return;
}
int mid=(l+r)/2;
init(p*2,l,mid);
init(p*2+1,mid+1,r);
it[p]=it[p*2]+it[p*2+1];
mx[p]=max(mx[p*2],mx[p*2+1]);
}
void dolazy(int p,int l,int r){
if(lazy[p]==0) return;
it[p]=0;
mx[p]=0;
if(l!=r){
lazy[p*2]=1;
lazy[p*2+1]=1;
}
lazy[p]=0;
}
void upd(int p,int l,int r,int pos,int val){
dolazy(p,l,r);
if(l>pos || r<pos) return;
if(l==pos && l==r){
it[p]=val;
mx[p]=val;
return;
}
int mid=(l+r)/2;
upd(p*2,l,mid,pos,val);
upd(p*2+1,mid+1,r,pos,val);
it[p]=it[p*2]+it[p*2+1];
mx[p]=max(mx[p*2],mx[p*2+1]);
}
void div(int p,int l,int r,int L,int R){
dolazy(p,l,r);
if(l>R || r<L || l>r) return;
if(l>=L && r<=R && mx[p]<=1 && k==1) return;
if(l>=L && r<=R && mx[p]<k){
if(mx[p]==0) return;
it[p]=0;
mx[p]=0;
if(l!=r){
lazy[p*2]=1;
lazy[p*2+1]=1;
}
return;
}
if(l==r){
it[p]=it[p]/(long long)k;
mx[p]=mx[p]/(long long)k;
return;
}
int mid=(l+r)/2;
div(p*2,l,mid,L,R);
div(p*2+1,mid+1,r,L,R);
it[p]=it[p*2]+it[p*2+1];
mx[p]=max(mx[p*2],mx[p*2+1]);
}
long long get(int p,int l,int r,int L,int R){
dolazy(p,l,r);
if(l>R || r<L || l>r) return 0;
if(l>=L && r<=R){
//cout<<l<<" "<<r<<" "<<it[p]<<endl;
return it[p];
}
int mid=(l+r)/2;
return (get(p*2,l,mid,L,R)+get(p*2+1,mid+1,r,L,R));
}
signed main(){
ios_base::sync_with_stdio(0);
cin>>n>>q>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
init(1,1,n);
int type;
for(int i=1;i<=q;i++){
cin>>type>>x>>y;
if(type==1){
upd(1,1,n,x,y);
}
else if(type==2){
div(1,1,n,x,y);
}
else{
cout<<get(1,1,n,x,y)<<"\n";
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
12332 KB |
Output is correct |
2 |
Correct |
0 ms |
12332 KB |
Output is correct |
3 |
Correct |
0 ms |
12332 KB |
Output is correct |
4 |
Correct |
9 ms |
12332 KB |
Output is correct |
5 |
Correct |
9 ms |
12332 KB |
Output is correct |
6 |
Correct |
6 ms |
12332 KB |
Output is correct |
7 |
Correct |
3 ms |
12332 KB |
Output is correct |
8 |
Correct |
9 ms |
12332 KB |
Output is correct |
9 |
Correct |
13 ms |
12332 KB |
Output is correct |
10 |
Correct |
9 ms |
12332 KB |
Output is correct |
11 |
Correct |
6 ms |
12332 KB |
Output is correct |
12 |
Correct |
19 ms |
12332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
0 ms |
0 KB |
-1: Interrupted system call
|
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
89 ms |
12332 KB |
Output is correct |
2 |
Correct |
26 ms |
12332 KB |
Output is correct |
3 |
Correct |
46 ms |
12332 KB |
Output is correct |
4 |
Correct |
163 ms |
12332 KB |
Output is correct |
5 |
Correct |
226 ms |
12332 KB |
Output is correct |
6 |
Correct |
406 ms |
12332 KB |
Output is correct |
7 |
Correct |
306 ms |
12332 KB |
Output is correct |
8 |
Correct |
299 ms |
12332 KB |
Output is correct |
9 |
Correct |
259 ms |
12332 KB |
Output is correct |
10 |
Correct |
203 ms |
12332 KB |
Output is correct |
11 |
Correct |
179 ms |
12332 KB |
Output is correct |
12 |
Correct |
303 ms |
12332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
256 ms |
12332 KB |
Output is correct |
2 |
Correct |
276 ms |
12332 KB |
Output is correct |
3 |
Correct |
266 ms |
12332 KB |
Output is correct |
4 |
Correct |
486 ms |
12332 KB |
Output is correct |
5 |
Correct |
476 ms |
12332 KB |
Output is correct |
6 |
Correct |
606 ms |
12332 KB |
Output is correct |
7 |
Correct |
579 ms |
12332 KB |
Output is correct |
8 |
Correct |
516 ms |
12332 KB |
Output is correct |
9 |
Correct |
666 ms |
12332 KB |
Output is correct |
10 |
Correct |
429 ms |
12332 KB |
Output is correct |
11 |
Correct |
286 ms |
12332 KB |
Output is correct |
12 |
Correct |
626 ms |
12332 KB |
Output is correct |