oj.uz

Submission #776400

# Submission time Handle Problem Language Result Execution time Memory
776400 2023-07-07T20:10:45 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++
75 / 100
 189 ms 14208 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(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 && k != 1) spray(a, b, 1, 1, n);
 		else cout << query(a, b, 1, 1, n) << '\n';
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12820 KB Output is correct
2 Incorrect 7 ms 12788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12884 KB Output is correct
2 Correct 14 ms 13140 KB Output is correct
3 Correct 17 ms 13212 KB Output is correct
4 Correct 38 ms 13100 KB Output is correct
5 Correct 48 ms 13696 KB Output is correct
6 Correct 47 ms 13608 KB Output is correct
7 Incorrect 53 ms 14208 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 66 ms 13424 KB Output is correct
2 Correct 71 ms 13388 KB Output is correct
3 Correct 86 ms 13332 KB Output is correct
4 Correct 93 ms 13296 KB Output is correct
5 Correct 104 ms 13824 KB Output is correct
6 Correct 121 ms 13800 KB Output is correct
7 Correct 99 ms 13896 KB Output is correct
8 Correct 141 ms 13900 KB Output is correct
9 Correct 122 ms 13876 KB Output is correct
10 Correct 142 ms 13900 KB Output is correct
11 Correct 102 ms 13920 KB Output is correct
12 Correct 189 ms 13960 KB Output is correct