oj.uz

Submission #482989

# Submission time Handle Problem Language Result Execution time Memory
482989 2021-10-27T09:29:09 Z S2speed Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 496 ms 96724 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94232 KB Output is correct
2 Incorrect 40 ms 94184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 353 ms 95660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 94396 KB Output is correct
2 Correct 105 ms 95176 KB Output is correct
3 Correct 120 ms 95280 KB Output is correct
4 Correct 281 ms 94916 KB Output is correct
5 Correct 408 ms 96312 KB Output is correct
6 Correct 419 ms 96328 KB Output is correct
7 Incorrect 401 ms 96320 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 95580 KB Output is correct
2 Correct 276 ms 95412 KB Output is correct
3 Correct 194 ms 95424 KB Output is correct
4 Correct 258 ms 95148 KB Output is correct
5 Correct 496 ms 96616 KB Output is correct
6 Correct 394 ms 96588 KB Output is correct
7 Correct 441 ms 96644 KB Output is correct
8 Correct 420 ms 96580 KB Output is correct
9 Correct 291 ms 96708 KB Output is correct
10 Correct 290 ms 96632 KB Output is correct
11 Correct 348 ms 96604 KB Output is correct
12 Correct 293 ms 96724 KB Output is correct