Submission #960309

#	Time	Username	Problem	Language	Result	Execution time	Memory
960309		pcc	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	156 ms	9860 KiB

sterilizing

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const ll mxn = 1e5+10;
int arr[mxn];

struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	pll seg[mxn*4];
	void build(int now,int l,int r){
		if(l == r){
			seg[now].fs = seg[now].sc = arr[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		seg[now].fs = seg[ls].fs+seg[rs].fs;
		seg[now].sc = max(seg[ls].sc,seg[rs].sc);
	}
	void chval(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now].fs = seg[now].sc = v;
			return;
		}
		if(mid>=p)chval(ls,l,mid,p,v);
		else chval(rs,mid+1,r,p,v);
		seg[now].fs = seg[ls].fs+seg[rs].fs;
		seg[now].sc = max(seg[ls].sc,seg[rs].sc);
	}
	void modify(int now,int l,int r,int s,int e,int k){
		if(k == 1)return;
		if(!seg[now].sc)return;
		if(l == r){
			seg[now].fs = seg[now].sc = seg[now].fs/k;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,k);
		if(mid<e)modify(rs,mid+1,r,s,e,k);
		seg[now].fs = seg[ls].fs+seg[rs].fs;
		seg[now].sc = max(seg[ls].sc,seg[rs].sc);
	}
	ll getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now].fs;
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return getval(ls,l,mid,s,e)+getval(rs,mid+1,r,s,e);
	}
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
};

SEG seg;
int N,Q,K;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q>>K;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	seg.build(0,1,N);
	while(Q--){
		int t,a,b;
		cin>>t>>a>>b;
		if(t == 1)seg.chval(0,1,N,a,b);
		else if(t == 2)seg.modify(0,1,N,a,b,K);
		else cout<<seg.getval(0,1,N,a,b)<<'\n';
	}
	return 0;
}

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