제출 #124822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
124822		tuanasanh	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	256 ms	4284 KiB

sterilizing

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define int long long
using namespace std;
const int N=1e5+50;
int q,n,k,type,u,v;
int a[N],sum[N*20];
void build(int id,int l,int r){
	if(l==r) sum[id]=a[l];
	if(l<r){
		int mid=(l+r)/2;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		sum[id]=sum[id*2]+sum[id*2+1];
	}
}
void boost(int id,int l,int r,int u,int v){
	if(l==r){
		sum[id]=v;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid) boost(id*2,l,mid,u,v);
	else boost(id*2+1,mid+1,r,u,v);
	sum[id]=sum[id*2]+sum[id*2+1];
}
void divide(int id,int l,int r,int u,int v){
	if(sum[id]==0||k==1) return;
	if(l==r){
		sum[id]/=k;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid) divide(id*2,l,mid,u,v);
	if(v>mid) divide(id*2+1,mid+1,r,u,v);
	sum[id]=sum[id*2]+sum[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 sum[id];
	int mid=(l+r)>>1;
	return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
signed main(){
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0); 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>>type>>u>>v;
		if(type==1) boost(1,1,n,u,v);
		else if(type==2) divide(1,1,n,u,v);
		else cout<<get(1,1,n,u,v)<<"\n";
	}
}

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