This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int Tree[3000000];
int N=(1<<(int)(log2(200000)));
int l,r;
int solve(int l1,int r1,int i){
if(l1>r||r1<l) return 0;
if(l1>=l&&r1<=r) return Tree[i];
return solve(l1,(r1+l1)/2,i*2)+solve(((l1+r1)/2)+1,r1,i*2+1);
}
signed main()
{
int n,k,q;
cin>>n>>q>>k;
int arr[n+1];
for(int i=0;i<n;i++){
cin>>arr[i];
Tree[i+N]=arr[i];
}
for(int i=N-1;i>=1;i--) Tree[i]=Tree[i*2]+Tree[i*2+1];
if(n<=3000&&q<=3000){
while(q--){
int type;
cin>>type;
if(type==1){
int indx,b;
cin>>indx>>b;
arr[indx-1]=b;
}
if(type==2){
int l,r;
cin>>l>>r;
for(int i=l-1;i<r;i++){
arr[i]=arr[i]/k;
}
}
if(type==3){
int l,r,sum=0;
cin>>l>>r;
for(int i=l-1;i<r;i++){
sum+=arr[i];
}
cout<<sum<<endl;
}
}
}
else if(k==1){
while(q--){
int type;
cin>>type;
if(type==1){
int indx,b;
cin>>indx>>b;
indx--;
Tree[indx+N]=arr[indx]=b;
indx+=N;
indx/=2;
while(indx!=0){
Tree[indx]=Tree[indx*2]+Tree[indx*2+1];
indx/=2;
}
}
if(type==3){
cin>>l>>r;
l--;
r--;
cout<<solve(0,N-1,1)<<endl;
}
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |