Submission #124812

#	Time	Username	Problem	Language	Result	Execution time	Memory
124812		nhimnam120	Sterilizing Spray (JOI15_sterilizing)	C++14	5 / 100	5099 ms	3320 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+5;
long long n,q,k;
long long inp[N];
long long node[N*4];
void build_tree(long long id,long long l ,long long r){
	if(l>r){
		return;
	}
	if(l==r){
		node[id] = inp[l];
		return;
	}
	int mid=(l+r)/2;
	build_tree(id*2,l,mid);
	build_tree(id*2+1,mid+1,r);
	node[id] = node[id*2] + node[id*2+1];
}
void upd(long long id, long long l, long long r ,long long pos, long long val){
	if(r<pos||l>pos){
		return;
	}
	if(l==r){
		node[id]=val;
		return;
	}
	long long mid=(l+r)/2;
	upd(id*2,l,mid,pos,val);
	upd(id*2+1,mid+1,r,pos,val);
	node[id] = node[id*2] + node[id*2+1];
}
void upd2(long long id, long long l ,long long r, long long u, long long v){
	if(r<u||l>v){
		return;
	}
	if(l==r){
		node[id] = node[id]/k;
		return;
	}
	long long mid=(l+r)/2;
	upd2(id*2,l,mid,u,v);
	upd2(id*2+1,mid+1,r,u,v);
	node[id] = node[id*2] + node[id*2+1];
}
long long get(long long id, long long l, long long r, long long u, long long v){
	if(l>v||r<u){
		return 0;
	}
	if(l>=u&&r<=v){
		return node[id];
	}
	long long mid = (l+r)/2;
	return get(id*2,l,mid,u,v) + get(id*2+1,mid+1,r,u,v);
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> k;
	for(int i=1;i<=n;i++){
		cin >> inp[i];
	}
	build_tree(1,1,n);
	int s,t,u;
	while(q--){
		cin >> s >> t >> u;
		if(s==1){
			upd(1,1,n,t,u);
		}
		if(s==2){
			upd2(1,1,n,t,u);
		}
		if(s==3){
			cout << get(1,1,n,t,u)<<endl;
		}
	}
}

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