Submission #1168511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168511		_rain_	Sterilizing Spray (JOI15_sterilizing)	C++20	80 / 100	5092 ms	4340 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)1e5;
int a[N+2];
int n,q,k;

namespace IT{
	#define lef(id) id*2
	#define rig(id) id*2+1
	const int MAXLOG=32;
	LL st[N*4+2];
	int stmax[N*4+2];
	void upd(int id,int l,int r,int pos,int val){
		if (l>pos||r<pos) return;
		if (l==r){
			st[id]=stmax[id]=val;
			return;
		}
		int m=(l+r)/2;
		upd(lef(id),l,m,pos,val);
		upd(rig(id),m+1,r,pos,val);
		st[id]=st[lef(id)]+st[rig(id)];
		stmax[id]=max(stmax[lef(id)],stmax[rig(id)]);
	}
	void upd_range(int id,int l,int r,int u,int v){
		if (l>v||r<u||stmax[id]==0) return;
		if (l==r) st[id]/=k,stmax[id]/=k;
		else{
			int m=(l+r)/2;
			upd_range(lef(id),l,m,u,v);
			upd_range(rig(id),m+1,r,u,v);
			st[id]=st[lef(id)]+st[rig(id)];
			stmax[id]=max(stmax[lef(id)],stmax[rig(id)]);
		}
	}
	LL Get(int id,int l,int r,int u,int v){
		if (l>v||r<u) return 0;
		if (u<=l&&r<=v) return st[id];
		int m=(l+r)/2;
		return Get(lef(id),l,m,u,v)+Get(rig(id),m+1,r,u,v);
	}
	
};

using namespace IT;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);

	
	cin>>n>>q>>k;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i) upd(1,1,n,i,a[i]);
	while(q--){
		int t,x,y; cin>>t>>x>>y;
		if (t==1) upd(1,1,n,x,y);
		else if (t==2){
			upd_range(1,1,n,x,y);
		}
		else {
			cout<<Get(1,1,n,x,y)<<'\n';
		}
	}
}

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