제출 #518367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518367		akshit	Sterilizing Spray (JOI15_sterilizing)	C++14	5 / 100	5064 ms	6544 KiB

sterilizing

// https://oj.uz/problem/view/JOI15_sterilizing
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<ll> seg;
vector<ll> arr;
int n,q;ll k;
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;
	
}
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];
}
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];
}
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;
	arr.resize(n+1);
	seg.resize(4*n);
	

	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