Submission #552714

#	Time	Username	Problem	Language	Result	Execution time	Memory
552714		dsyz	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	279 ms	16476 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
/* use "brute force" using point update for divide since
the log2(10^9) <= 32 so it is small enough to divide individually, 
just stop going down when there is v = 0 in the divide function
Also, if K == 1, then dont divide since it will all the way down
as v would not be log() at all so would TLE
* */
ll N,Q,K;
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) >> 1;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll newvalue){
		if(s == e){
			v = newvalue;
		}else{
			if(x >= m + 1) r -> update(x,newvalue);
			else if(x <= m) l -> update(x,newvalue);
			v = l->v + r->v;
		}
	}
	void spray(ll x,ll y){
		if(K == 1) return;
		if(s == e){
			v /= K;
		}else if(s == x && e == y){
			if(v == 0) return;
			l->spray(x,m);
			r->spray(m + 1,y);
			v = l->v + r->v;
		}else{
			if(x >= m + 1) r -> spray(x,y);
			else if(y <= m) l -> spray(x,y);
			else l -> spray(x,m), r -> spray(m + 1,y);
			v = l->v + r->v;
		}
	}
	long long query(ll x,ll y){
		if(s == x && e == y) return v;
		else{
			if(x >= m + 1) return r -> query(x,y);
			else if(y <= m) return l -> query(x,y);
			else return l -> query(x,m) + r -> query(m + 1,y);
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>Q>>K;
	root = new node(0,N + 5);
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
		root -> update(i,arr[i]);
	}
	for(ll i = 0;i < Q;i++){
		ll s,t,u;
		cin>>s>>t>>u;
		if(s == 1){
			t--;
			root -> update(t,u);
		}else if(s == 2){
			t--;
			u--;
			root -> spray(t,u);
		}else if(s == 3){
			t--;
			u--;
			cout<<root -> query(t,u)<<'\n';
		}
	}
}

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