oj.uz

답안 #482990

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482990 2021-10-27T09:30:19 Z S2speed Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 409 ms 96964 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--;
			if(k > 1) st.div(l , r);
		}
		if(t == 3){
			ll l , r;
			cin>>l>>r; l--;
			cout<<st.cal(l , r)<<'\n';
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 94148 KB Output is correct
2 Correct 37 ms 94284 KB Output is correct
3 Correct 37 ms 94232 KB Output is correct
4 Correct 39 ms 94272 KB Output is correct
5 Correct 41 ms 94260 KB Output is correct
6 Correct 52 ms 94304 KB Output is correct
7 Correct 41 ms 94280 KB Output is correct
8 Correct 43 ms 94308 KB Output is correct
9 Correct 40 ms 94284 KB Output is correct
10 Correct 41 ms 94296 KB Output is correct
11 Correct 41 ms 94324 KB Output is correct
12 Correct 41 ms 94320 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 95676 KB Output is correct
2 Correct 117 ms 95664 KB Output is correct
3 Correct 134 ms 96488 KB Output is correct
4 Correct 164 ms 96588 KB Output is correct
5 Correct 189 ms 96672 KB Output is correct
6 Correct 179 ms 96708 KB Output is correct
7 Correct 183 ms 96692 KB Output is correct
8 Correct 196 ms 96708 KB Output is correct
9 Correct 180 ms 96716 KB Output is correct
10 Correct 206 ms 96964 KB Output is correct
11 Correct 188 ms 96820 KB Output is correct
12 Correct 184 ms 96768 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 94320 KB Output is correct
2 Correct 95 ms 95208 KB Output is correct
3 Correct 117 ms 95372 KB Output is correct
4 Correct 226 ms 94720 KB Output is correct
5 Correct 347 ms 96484 KB Output is correct
6 Correct 409 ms 96320 KB Output is correct
7 Correct 160 ms 96360 KB Output is correct
8 Correct 342 ms 96488 KB Output is correct
9 Correct 248 ms 96372 KB Output is correct
10 Correct 258 ms 96360 KB Output is correct
11 Correct 253 ms 96324 KB Output is correct
12 Correct 249 ms 96380 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 95376 KB Output is correct
2 Correct 253 ms 95484 KB Output is correct
3 Correct 177 ms 95404 KB Output is correct
4 Correct 239 ms 95044 KB Output is correct
5 Correct 364 ms 96532 KB Output is correct
6 Correct 347 ms 96544 KB Output is correct
7 Correct 353 ms 96456 KB Output is correct
8 Correct 350 ms 96532 KB Output is correct
9 Correct 255 ms 96708 KB Output is correct
10 Correct 265 ms 96544 KB Output is correct
11 Correct 277 ms 96584 KB Output is correct
12 Correct 267 ms 96536 KB Output is correct