Submission #940551

#	Time	Username	Problem	Language	Result	Execution time	Memory
940551		Alexabcde1	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	196 ms	6268 KiB

sterilizing

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
long long n,q,k,a[100005],seg[400005],aa,bb,cc;
void build(long long ind,long long l,long long r){
	if (r<l) return;
	if (l==r){
		seg[ind]=a[l]; return;
	}
	long long mid=(l+r)/2;
	build(ind*2,l,mid);
	build(ind*2+1,mid+1,r);
	seg[ind]=seg[ind*2]+seg[ind*2+1];
	return;
}
void update(long long ind,long long l,long long r){
	if (r<bb) return;
	if (cc<l) return;
	if (r<l)  return;
	if (seg[ind]==0 || k==1) return;
	if ((bb<=l) && (r<=cc)){
		if (l==r){
			seg[ind]/=k;
		}
		else {
			long long mid=(l+r)/2;
			update(ind*2,l,mid);
			update(ind*2+1,mid+1,r);
			seg[ind]=seg[ind*2]+seg[ind*2+1];
		}
	}
	else {
		long long mid=(l+r)/2;
		update(ind*2,l,mid);
		update(ind*2+1,mid+1,r);
		seg[ind]=seg[ind*2]+seg[ind*2+1];
	}
	return;
}

void update2(long long ind,long long l,long long r){
	if (r<bb) return;
	if (bb<l) return;
	if (l==r){
		seg[ind]=cc;
	}
	else {
		long long mid=(l+r)/2;
		update2(ind*2,l,mid);
		update2(ind*2+1,mid+1,r);
		seg[ind]=seg[ind*2]+seg[ind*2+1];
	}
	return;
}

long long sum(long long ind,long long l,long long r){
	if ((r<bb) || (cc<l)) return 0;
	if (bb<=l && r<=cc){
		return seg[ind];
	}
	else {
		long long mid=(l+r)/2;
		return sum(ind*2,l,mid)+sum(ind*2+1,mid+1,r);
	}
}
int main(){
	ios::sync_with_stdio(false);
	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>>aa>>bb>>cc;
		if (aa==1) update2(1,1,n);
		if (aa==2) update(1,1,n);
		if (aa==3) cout<<sum(1,1,n)<<endl;
	}
}

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