Submission #124816

#	Time	Username	Problem	Language	Result	Execution time	Memory
124816		nhimnam120	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	502 ms	3960 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,k;
int a[100005],node[400004];
void build(int i,int l,int r){
	if(l>r) return;
	if(l==r){
		node[i]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	node[i]=node[i*2]+node[i*2+1];
}
void update1(int i,int l,int r,int pos,int val){
	if(l>r||pos<l||pos>r) return;
	if(l==r){
		if(l==pos){
			a[l]=val;
			node[i]=val;
			return;
		}
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid) update1(i*2,l,mid,pos,val);
	else update1(i*2+1,mid+1,r,pos,val);
	node[i]=node[i*2]+node[i*2+1];
}
void update2(int i,int l,int r,int u,int v){
	if(node[i]==0||k==1) return;
	if(l==r){
		node[i]/=k;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid) update2(i*2,l,mid,u,v);
	if(mid<v) update2(i*2+1,mid+1,r,u,v);
	node[i]=node[i*2]+node[i*2+1];
}
int get(int i,int l,int r,int u,int v){
	if(l>r||u>r||v<l) return 0;
	if(u<=l&&v>=r) return node[i];
	int mid=(l+r)/2;
	int ans=0;
	if(u<=mid) ans+=get(i*2,l,mid,u,v);
	if(mid<v) ans+=get(i*2+1,mid+1,r,u,v);
	return ans;  
}
signed main(){
	cin>>n>>q>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(q--){
		int s;
		cin>>s;
		if(s==1){
			int u,v;
			cin>>u>>v;
			update1(1,1,n,u,v);
		}
		else if(s==2){
			int l,r;
			cin>>l>>r;
			update2(1,1,n,l,r);
		}
		else if(s==3){
			int l,r;
			cin>>l>>r;
			cout<<get(1,1,n,l,r)<<endl;
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75