Submission #518371

#	Time	Username	Problem	Language	Result	Execution time	Memory
518371		akshit	Sterilizing Spray (JOI15_sterilizing)	C++14	5 / 100	5057 ms	3612 KiB

sterilizing

// https://oj.uz/problem/view/JOI15_sterilizing
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll seg[4000003];
ll arr[1000003];
int n,q;ll k;
inline void build(int l,int r,int node){
	
	if(l==r){seg[node]=arr[l];return;}
	int mid=(l+r)>>1;
	int L=node<<1;int R=L|1;
	build(l,mid,L);build(mid+1,r,R);
	seg[node]=seg[L]+seg[R];
	// cout<<l<<" "<<r<<" "<<node<<" "<<seg[node]<<endl;
	
}
inline void fix(int l,int r,int node,int p,ll val){
	if(l==r){seg[node]=arr[l]=val;return;}
	int mid=(l+r)>>1;
	int L=node<<1;int R=L|1;
	if(p<=mid)fix(l,mid,L,p,val);
	else fix(mid+1,r,R,p,val);
	seg[node]=seg[L]+seg[R];
}
inline void upd(int l,int r,int node,int i,int j){
	// cout<<i<<" "<<j<<endl;
	if(l==r){

		arr[l]/=k;
		seg[node]=arr[l];return;
	}
	int L=node<<1;int R=L|1;
	int mid=(l+r)>>1;
	if(mid<i){upd(mid+1,r,R,i,j);}
	else if(mid>=j){upd(l,mid,L,i,j);}
	else {upd(l,mid,L,i,mid);
	upd(mid+1,r,R,mid+1,j);}
	seg[node]=seg[L]+seg[R];
}
inline ll query(int l,int r,int node,int i,int j){

	if(l>=i &&j>=r){return seg[node];}
	if(r<i || l>j)return 0;
	int L=node<<1;int R=L|1;
	int mid=(l+r)>>1;
	if(mid<i){return query(mid+1,r,R,i,j);}
	if(mid>=j){return query(l,mid,L,i,j);}
	return query(l,mid,L,i,mid)+query(mid+1,r,R,mid+1,j);

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	cin>>n>>q>>k;
	
	

	for(int i=1;i<=n;i++)cin>>arr[i];

	build(1,n,1);
	int t,a;ll b;
	// cout<<query(1,n,1,9,12)<<endl;
	for(int i=0;i<q;i++){
		cin>>t>>a>>b;
		if(t==1){
			fix(1,n,1,a,b);
			// cout<<"f "<<a<<" "<<b<<" "<<query(1,n,1,1,n)<<endl;
		}else if(t==2){
			upd(1,n,1,a,b);
			// cout<<"u "<<a<<" "<<b<<" "<<query(1,n,1,1,n)<<endl;
		}else {cout<<query(1,n,1,a,b)<<endl;}
	}
	return 0;
}

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