Submission #124817

#	Time	Username	Problem	Language	Result	Execution time	Memory
124817		nhimnam120	Sterilizing Spray (JOI15_sterilizing)	C++14	10 / 100	157 ms	2176 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,k;
int inp[N];
int node[N*4];
void build_tree(int id,int l ,int 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(int id, int l, int r ,int pos, int val){
	if(r<pos||l>pos){
		return;
	}
	if(l==r){
		node[id]=val;
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid){
		upd(id*2,l,mid,pos,val);
	}
	else{
		upd(id*2+1,mid+1,r,pos,val);
	}
	node[id] = node[id*2] + node[id*2+1];
}
void upd2(int id, int l ,int r, int u, int v){
	if(node[id]==0||k==1){
		return;
	}
	if(r<u||l>v){
		return;
	}
	if(l==r){
		node[id] = node[id]/k;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid){
		upd2(id*2,l,mid,u,v);
	}
	if(v>mid){
		upd2(id*2+1,mid+1,r,u,v);
	}
	node[id] = node[id*2] + node[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 node[id];
	}
	int mid = (l+r)/2;
	int ans=0;
	if(u<=mid){
		ans = ans + get(id*2,l,mid,u,v);
	}
	if(v>mid){
		ans = ans + get(id*2+1,mid+1,r,u,v);
	}
	return ans;
}
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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75