Submission #776380

#	Time	Username	Problem	Language	Result	Execution time	Memory
776380		Hacv16	Sterilizing Spray (JOI15_sterilizing)	C++17	80 / 100	5065 ms	5500 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAX = 1e5 + 15;
 
inline ll get(void) {
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    ll ret = 0;
    while (c >= '0' && c <= '9')
        ret = ret * 10 + (c - '0'), c = getchar();
    return ret;
}
 
ll n, q, k, v[MAX], seg[4 * MAX], mx[4 * MAX];
 
void build(int p, int l, int r){
	if(l == r){
		seg[p] = v[l];
		mx[p] = v[l];
		return;
	}
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	build(e, l, m); build(d, m + 1, r);
 
	seg[p] = seg[e] + seg[d];
	mx[p] = max(mx[e], mx[d]);
}
 
ll query(int a, int b, int p, int l, int r){
	if(a > r || b < l || seg[p] == 0 || mx[p] == 0) return 0;
	if(a <= l && r <= b) return seg[p];
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	return query(a, b, e, l, m) + query(a, b, d, m + 1, r);
}
 
void update(int i, ll x, int p, int l, int r){
	if(l == r){
		seg[p] = x;	
		mx[p] = x;
		return;
	}
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
 
	if(i <= m) update(i, x, e, l, m);
	else update(i, x, d, m + 1, r);
 
	seg[p] = seg[e] + seg[d];
	mx[p] = max(mx[e], mx[d]);
}
 
void spray(int a, int b, int p, int l, int r){
	if(seg[p] == 0 || mx[p] == 0 || a > r || b < l) return;
	if(l == r){ seg[p] /= k; mx[p] /= k; return; }
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	spray(a, b, e, l, m); spray(a, b, d, m + 1, r);
 
	seg[p] = seg[e] + seg[d];
	mx[p] = max(mx[e], mx[d]);
}
 
int32_t main(void){
	n = get(); q = get(); k = get();
 
	for(int i = 1; i <= n; i++) v[i] = get();
 
	build(1, 1, n);
 
	while(q--){
		int op = get();
 
		if(op == 1){
			int i = get(), x = get();
			update(i, x, 1, 1, n);
 
		}else if(op == 2){
			int l = get(), r = get();
			spray(l, r, 1, 1, n);
 
		}else{
			int l = get(), r = get();
			cout << query(l, r, 1, 1, n) << '\n';
		}
	}
 
	exit(0);
}

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