oj.uz

Submission #776404

# Submission time Handle Problem Language Result Execution time Memory
776404 2023-07-07T20:12:20 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 209 ms 14140 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;
const int MAX = 2e5 + 10;
 
struct Node{
	ll sum, mx;
	Node(ll a = 0, ll b = 0) : sum(a), mx(b) { }

	Node operator + (Node other){
		return Node(sum + other.sum, max(mx, other.mx));
	}

} seg[4 * MAX];

ll n, q, k, v[4 * MAX];
 
void build(int p, int l, int r){
	if(l == r){
		seg[p] = Node(v[l], 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];
}
 
ll query(int a, int b, int p, int l, int r){
	if(a > r || b < l) return 0;
	if(a <= l && r <= b) return seg[p].sum;
 
	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(i < l || i > r) return;
	if(l == r){
		seg[p] = Node(x, 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];
}
 
void spray(int a, int b, int p, int l, int r){
	if(k == 1) return;
	if(seg[p].mx == 0 || a > r || b < l) return;
	if(l == r){ seg[p].sum /= k; seg[p].mx /= 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];
}
 
int32_t main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> q >> k;
 
	for(int i = 1; i <= n; i++) cin >> v[i];
 
	build(1, 1, n);
 
	while(q--){
		int op, a, b; cin >> op >> a >> b;

		if(op == 1) update(a, b, 1, 1, n);
		else if(op == 2) spray(a, b, 1, 1, n);
 		else cout << query(a, b, 1, 1, n) << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 7 ms 12840 KB Output is correct
4 Correct 9 ms 12868 KB Output is correct
5 Correct 9 ms 12884 KB Output is correct
6 Correct 8 ms 12884 KB Output is correct
7 Correct 9 ms 12884 KB Output is correct
8 Correct 9 ms 12772 KB Output is correct
9 Correct 9 ms 12836 KB Output is correct
10 Correct 9 ms 12856 KB Output is correct
11 Correct 8 ms 12884 KB Output is correct
12 Correct 9 ms 12884 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 13676 KB Output is correct
2 Correct 39 ms 13520 KB Output is correct
3 Correct 39 ms 13800 KB Output is correct
4 Correct 42 ms 13932 KB Output is correct
5 Correct 51 ms 14112 KB Output is correct
6 Correct 48 ms 14112 KB Output is correct
7 Correct 48 ms 14080 KB Output is correct
8 Correct 48 ms 14028 KB Output is correct
9 Correct 51 ms 14024 KB Output is correct
10 Correct 45 ms 14020 KB Output is correct
11 Correct 46 ms 14140 KB Output is correct
12 Correct 45 ms 14028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12940 KB Output is correct
2 Correct 14 ms 13136 KB Output is correct
3 Correct 18 ms 13140 KB Output is correct
4 Correct 39 ms 13056 KB Output is correct
5 Correct 47 ms 13652 KB Output is correct
6 Correct 47 ms 13652 KB Output is correct
7 Correct 41 ms 13804 KB Output is correct
8 Correct 46 ms 13652 KB Output is correct
9 Correct 43 ms 13664 KB Output is correct
10 Correct 42 ms 13648 KB Output is correct
11 Correct 43 ms 13660 KB Output is correct
12 Correct 43 ms 13652 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 13332 KB Output is correct
2 Correct 76 ms 13468 KB Output is correct
3 Correct 93 ms 13300 KB Output is correct
4 Correct 96 ms 13296 KB Output is correct
5 Correct 109 ms 13892 KB Output is correct
6 Correct 126 ms 13892 KB Output is correct
7 Correct 105 ms 13896 KB Output is correct
8 Correct 172 ms 13912 KB Output is correct
9 Correct 158 ms 13876 KB Output is correct
10 Correct 156 ms 13872 KB Output is correct
11 Correct 112 ms 13928 KB Output is correct
12 Correct 209 ms 13880 KB Output is correct