Submission #124852

#	Time	Username	Problem	Language	Result	Execution time	Memory
124852		TienDungz	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	265 ms	6008 KiB

sterilizing

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,q,u,v,x,st[405000],gt[100005];
void build(int index,int l,int r)
{
	if(l>r) return;
	if(l==r) 
	{
		st[index]=gt[l];
		return;
	}
	int mid=(l+r)/2;
	build(index*2,l,mid);
	build(index*2+1,mid+1,r);
	st[index]=st[index*2]+st[index*2+1];
}
void update1(int index,int l,int r,int pos,int val)
{
	if(r<pos||l>pos) return;
	if(l==r&&l==pos)
	{
		st[index]=val;
		return;
	}
	int mid=(l+r)/2;
	update1(index*2,l,mid,pos,val);
	update1(index*2+1,mid+1,r,pos,val);
	st[index]=st[index*2]+st[index*2+1];
}	
void update2(int index,int l,int r,int u,int v)
{
	if(r<u||l>v||st[index]==0||k==1) return;
	if(l==r)
	{
		st[index]=st[index]/k;
		return;
	}
	int mid=(l+r)/2;
	update2(index*2,l,mid,u,v);
	update2(index*2+1,mid+1,r,u,v);
	st[index]=st[index*2]+st[index*2+1];
}
int get(int index,int l,int r,int u,int v)
{
	if(r<u||l>v) return 0;
	if(u<=l&&r<=v) return st[index];
	int mid=(l+r)/2;
	return get(index*2,l,mid,u,v)+get(index*2+1,mid+1,r,u,v);
}
signed 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>>gt[i];
	}
	build(1,1,n);
	while(q--)
	{
		int type;
		cin>>type;
		if(type==1)
		{
			int a,b;
			cin>>a>>b;
			update1(1,1,n,a,b);
		}
		else if(type==2)
		{
			int l,r;
			cin>>l>>r;
			update2(1,1,n,l,r);
		}
		else if(type==3)
		{
			int l,r;
			cin>>l>>r;
			cout<<get(1,1,n,l,r)<<"\n";
		}
	}
}

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