oj.uz

Submission #776380

# Submission time Handle Problem Language Result Execution time Memory
776380 2023-07-07T19:09:30 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 5500 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAX = 1e5 + 15;
 
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;
}
 
ll n, q, k, v[MAX], seg[4 * MAX], mx[4 * MAX];
 
void build(int p, int l, int r){
	if(l == r){
		seg[p] = v[l];
		mx[p] = 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];
	mx[p] = max(mx[e], mx[d]);
}
 
ll query(int a, int b, int p, int l, int r){
	if(a > r || b < l || seg[p] == 0 || mx[p] == 0) return 0;
	if(a <= l && r <= b) return seg[p];
 
	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(l == r){
		seg[p] = x;	
		mx[p] = 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];
	mx[p] = max(mx[e], mx[d]);
}
 
void spray(int a, int b, int p, int l, int r){
	if(seg[p] == 0 || mx[p] == 0 || a > r || b < l) return;
	if(l == r){ seg[p] /= k; mx[p] /= 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];
	mx[p] = max(mx[e], mx[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();
 
		if(op == 1){
			int i = get(), x = get();
			update(i, x, 1, 1, n);
 
		}else if(op == 2){
			int l = get(), r = get();
			spray(l, r, 1, 1, n);
 
		}else{
			int l = get(), r = get();
			cout << query(l, r, 1, 1, n) << '\n';
		}
	}
 
	exit(0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 5 ms 2644 KB Output is correct
3 Correct 6 ms 2644 KB Output is correct
4 Correct 18 ms 1576 KB Output is correct
5 Correct 22 ms 5204 KB Output is correct
6 Correct 23 ms 5264 KB Output is correct
7 Execution timed out 5047 ms 5464 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2892 KB Output is correct
2 Correct 52 ms 2876 KB Output is correct
3 Correct 80 ms 2732 KB Output is correct
4 Correct 74 ms 1848 KB Output is correct
5 Correct 97 ms 5364 KB Output is correct
6 Correct 94 ms 5440 KB Output is correct
7 Correct 74 ms 5452 KB Output is correct
8 Correct 132 ms 5432 KB Output is correct
9 Correct 111 ms 5432 KB Output is correct
10 Correct 125 ms 5500 KB Output is correct
11 Correct 82 ms 5444 KB Output is correct
12 Correct 172 ms 5436 KB Output is correct