oj.uz

Submission #776375

# Submission time Handle Problem Language Result Execution time Memory
776375 2023-07-07T19:04:34 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 3460 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];

void build(int p, int l, int r){
	if(l == r){
		seg[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];
}

ll query(int a, int b, int p, int l, int r){
	if(a > r || b < l || seg[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;	
		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] == 0 || a > r || b < l) return;
	if(l == r){ seg[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];
}

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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 404 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4014 ms 2268 KB Output is correct
2 Correct 2451 ms 1980 KB Output is correct
3 Correct 4134 ms 3240 KB Output is correct
4 Execution timed out 5081 ms 3408 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 4 ms 1688 KB Output is correct
3 Correct 6 ms 1620 KB Output is correct
4 Correct 17 ms 980 KB Output is correct
5 Correct 20 ms 3156 KB Output is correct
6 Correct 19 ms 3156 KB Output is correct
7 Execution timed out 5079 ms 3244 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1872 KB Output is correct
2 Correct 44 ms 1896 KB Output is correct
3 Correct 55 ms 1744 KB Output is correct
4 Correct 58 ms 1264 KB Output is correct
5 Correct 64 ms 3324 KB Output is correct
6 Correct 77 ms 3396 KB Output is correct
7 Correct 76 ms 3400 KB Output is correct
8 Correct 93 ms 3428 KB Output is correct
9 Correct 81 ms 3408 KB Output is correct
10 Correct 94 ms 3436 KB Output is correct
11 Correct 65 ms 3352 KB Output is correct
12 Correct 130 ms 3460 KB Output is correct