oj.uz

Submission #776399

# Submission time Handle Problem Language Result Execution time Memory
776399 2023-07-07T20:09:15 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++
80 / 100
 5000 ms 13928 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) 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 7 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 9 ms 12756 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 9 ms 12812 KB Output is correct
7 Correct 8 ms 12876 KB Output is correct
8 Correct 10 ms 12884 KB Output is correct
9 Correct 9 ms 12884 KB Output is correct
10 Correct 10 ms 12884 KB Output is correct
11 Correct 8 ms 12784 KB Output is correct
12 Correct 8 ms 12884 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 13580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12884 KB Output is correct
2 Correct 13 ms 13140 KB Output is correct
3 Correct 17 ms 13220 KB Output is correct
4 Correct 39 ms 13076 KB Output is correct
5 Correct 46 ms 13676 KB Output is correct
6 Correct 47 ms 13676 KB Output is correct
7 Execution timed out 5040 ms 13740 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13380 KB Output is correct
2 Correct 74 ms 13460 KB Output is correct
3 Correct 90 ms 13336 KB Output is correct
4 Correct 88 ms 13312 KB Output is correct
5 Correct 101 ms 13860 KB Output is correct
6 Correct 118 ms 13900 KB Output is correct
7 Correct 97 ms 13904 KB Output is correct
8 Correct 149 ms 13880 KB Output is correct
9 Correct 123 ms 13896 KB Output is correct
10 Correct 140 ms 13928 KB Output is correct
11 Correct 101 ms 13828 KB Output is correct
12 Correct 211 ms 13876 KB Output is correct