oj.uz

Submission #776402

# Submission time Handle Problem Language Result Execution time Memory
776402 2023-07-07T20:11:55 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++
100 / 100
 236 ms 14972 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 9 ms 12760 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 8 ms 12884 KB Output is correct
5 Correct 9 ms 12816 KB Output is correct
6 Correct 8 ms 12880 KB Output is correct
7 Correct 12 ms 12884 KB Output is correct
8 Correct 8 ms 12788 KB Output is correct
9 Correct 9 ms 12884 KB Output is correct
10 Correct 8 ms 12884 KB Output is correct
11 Correct 11 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 46 ms 13620 KB Output is correct
2 Correct 41 ms 14016 KB Output is correct
3 Correct 38 ms 14260 KB Output is correct
4 Correct 49 ms 14608 KB Output is correct
5 Correct 59 ms 14912 KB Output is correct
6 Correct 54 ms 14892 KB Output is correct
7 Correct 54 ms 14904 KB Output is correct
8 Correct 57 ms 14972 KB Output is correct
9 Correct 50 ms 14960 KB Output is correct
10 Correct 56 ms 14932 KB Output is correct
11 Correct 53 ms 14952 KB Output is correct
12 Correct 51 ms 14916 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12936 KB Output is correct
2 Correct 14 ms 13148 KB Output is correct
3 Correct 22 ms 13124 KB Output is correct
4 Correct 41 ms 13068 KB Output is correct
5 Correct 51 ms 13684 KB Output is correct
6 Correct 47 ms 13668 KB Output is correct
7 Correct 47 ms 13804 KB Output is correct
8 Correct 56 ms 14484 KB Output is correct
9 Correct 53 ms 14516 KB Output is correct
10 Correct 52 ms 14560 KB Output is correct
11 Correct 47 ms 14472 KB Output is correct
12 Correct 48 ms 14512 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 13372 KB Output is correct
2 Correct 76 ms 13464 KB Output is correct
3 Correct 99 ms 13336 KB Output is correct
4 Correct 117 ms 13324 KB Output is correct
5 Correct 122 ms 13880 KB Output is correct
6 Correct 129 ms 13888 KB Output is correct
7 Correct 111 ms 13784 KB Output is correct
8 Correct 159 ms 13880 KB Output is correct
9 Correct 143 ms 13920 KB Output is correct
10 Correct 166 ms 13884 KB Output is correct
11 Correct 118 ms 13896 KB Output is correct
12 Correct 236 ms 13920 KB Output is correct