Submission #482989

#	Time	Username	Problem	Language	Result	Execution time	Memory
482989		S2speed	Sterilizing Spray (JOI15_sterilizing)	C++17	75 / 100	496 ms	96724 KiB

sterilizing

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 1e5 + 16 , md = 1e9 + 7 , inf = 2e16;

ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll n , q , k;

struct segtree {

	ll sz = 1;
	ll val[4 * maxn][30];
	vector<ll> laz;

	void init(ll n){
		while(sz < n) sz <<= 1;
		memset(val , 0 , sizeof(val));
		laz.assign(sz << 1 , 0);
		return;
	}

	void shift(ll x , ll lx , ll rx){
		ll h = laz[x];
		laz[x] = 0;
		if(!h) return;
		if(h >= 30){
			for(ll j = 0 ; j < 30 ; j++) val[x][j] = 0;
		} else {
			for(ll j = 0 ; j + h < 30 ; j++){
				val[x][j] = val[x][j + h];
			}
			for(ll j = 30 - h ; j < 30 ; j++) val[x][j] = 0;
		}
		if(rx - lx == 1) return;
		ll ln = (x << 1) + 1 , rn = ln + 1;
		laz[ln] += h; laz[rn] += h;
		return;
	}
	
	void set(ll i , ll r , ll x , ll lx , ll rx){
		shift(x , lx , rx);
		if(rx <= i || lx > i) return;
		if(rx - lx == 1){
			val[x][0] = r;
			for(ll j = 1 ; j < 30 ; j++){
				val[x][j] = val[x][j - 1] / k;
			}
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		set(i , r , ln , lx , m); set(i , r , rn , m , rx);
		for(ll j = 0 ; j < 30 ; j++){
			val[x][j] = val[ln][j] + val[rn][j];
		}
		return;
	}

	void set(ll i , ll r){
		set(i , r , 0 , 0 , sz);
		return;
	}

	void div(ll l , ll r , ll x , ll lx , ll rx){
		shift(x , lx , rx);
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			laz[x] = 1;
			shift(x , lx , rx);
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		div(l , r , ln , lx , m); div(l , r , rn , m , rx);
		for(ll j = 0 ; j < 30 ; j++){
			val[x][j] = val[ln][j] + val[rn][j];
		}
		return;
	}

	void div(ll l , ll r){
		div(l , r , 0 , 0 , sz);
		return;
	}

	ll cal(ll l , ll r , ll x , ll lx , ll rx){
		shift(x , lx , rx);
		if(rx <= l || lx >= r) return 0;
		if(rx <= r && lx >= l) return val[x][0];
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		ll a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
		return a + b;
	}

	ll cal(ll l , ll r){
		return cal(l , r , 0 , 0 , sz);
	}

};

segtree st;

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

	cin>>n>>q>>k;
	st.init(n);
	for(ll i = 0 ; i < n ; i++){
		ll h;
		cin>>h;
		st.set(i , h);
	}
	for(ll e = 0 ; e < q ; e++){
		ll t;
		cin>>t;
		if(t == 1){
			ll i , r;
			cin>>i>>r; i--;
			st.set(i , r);
		}
		if(t == 2){
			ll l , r;
			cin>>l>>r; l--;
			st.div(l , r);
		}
		if(t == 3){
			ll l , r;
			cin>>l>>r; l--;
			cout<<st.cal(l , r)<<'\n';
		}
	}
	return 0;
}

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