oj.uz

Submission #776398

# Submission time Handle Problem Language Result Execution time Memory
776398 2023-07-07T20:07:14 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 13900 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAX = 2e5 + 10;
 
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;
}
 
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){
	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(), a = get(), b = get();
		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 6 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 7 ms 12756 KB Output is correct
5 Correct 8 ms 12756 KB Output is correct
6 Correct 8 ms 12756 KB Output is correct
7 Correct 8 ms 12756 KB Output is correct
8 Correct 7 ms 12756 KB Output is correct
9 Correct 8 ms 12756 KB Output is correct
10 Correct 7 ms 12756 KB Output is correct
11 Correct 7 ms 12756 KB Output is correct
12 Correct 8 ms 12868 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12884 KB Output is correct
2 Correct 11 ms 13188 KB Output is correct
3 Correct 12 ms 13108 KB Output is correct
4 Correct 27 ms 13056 KB Output is correct
5 Correct 33 ms 13640 KB Output is correct
6 Correct 33 ms 13624 KB Output is correct
7 Execution timed out 5085 ms 13620 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 13452 KB Output is correct
2 Correct 64 ms 13436 KB Output is correct
3 Correct 84 ms 13304 KB Output is correct
4 Correct 83 ms 13340 KB Output is correct
5 Correct 94 ms 13872 KB Output is correct
6 Correct 111 ms 13836 KB Output is correct
7 Correct 94 ms 13816 KB Output is correct
8 Correct 138 ms 13868 KB Output is correct
9 Correct 117 ms 13868 KB Output is correct
10 Correct 136 ms 13848 KB Output is correct
11 Correct 96 ms 13900 KB Output is correct
12 Correct 217 ms 13860 KB Output is correct