Submission #124821

#	Time	Username	Problem	Language	Result	Execution time	Memory
124821		tuanasanh	Sterilizing Spray (JOI15_sterilizing)	C++14	10 / 100	163 ms	2316 KiB

sterilizing

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
const int N=1e5+50;
int q,n,k,type,u,v;
int a[N],sum[N*20];
void build(int id,int l,int r){
	if(l==r) sum[id]=a[l];
	if(l<r){
		int mid=(l+r)/2;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		sum[id]=sum[id*2]+sum[id*2+1];
	}
}
void boost(int id,int l,int r,int u,int v){
	if(l==r){
		sum[id]=v;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid) boost(id*2,l,mid,u,v);
	else boost(id*2+1,mid+1,r,u,v);
	sum[id]=sum[id*2]+sum[id*2+1];
}
void divide(int id,int l,int r,int u,int v){
	if(sum[id]==0||k==1) return;
	if(l==r){
		sum[id]/=k;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid) divide(id*2,l,mid,u,v);
	if(v>mid) divide(id*2+1,mid+1,r,u,v);
	sum[id]=sum[id*2]+sum[id*2+1];
}
int get(int id,int l,int r,int u,int v){
	if(l>v||r<u) return 0;
	if(l>=u&&r<=v) return sum[id];
	int mid=(l+r)>>1;
	return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
signed main(){
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>q>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while(q--){
		cin>>type>>u>>v;
		if(type==1) boost(1,1,n,u,v);
		else if(type==2) divide(1,1,n,u,v);
		else cout<<get(1,1,n,u,v)<<endl;
	}
}

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