oj.uz

Submission #776371

# Submission time Handle Problem Language Result Execution time Memory
776371 2023-07-07T18:55:16 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 5872 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 1e5 + 15;

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) 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(i > r || i < l) return;
	if(l == r){
		seg[p] = x;	
		return;
	}

	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	update(i, x, e, l, m); 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){
	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; cin >> op;

		if(op == 1){
			ll i, x; cin >> i >> x;
			update(i, x, 1, 1, n);

		}else if(op == 2){
			ll l, r; cin >> l >> r;
			spray(l, r, 1, 1, n);

		}else{
			ll l, r; cin >> l >> r;
			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 340 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 404 KB Output is correct
8 Correct 3 ms 464 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 464 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3923 ms 4128 KB Output is correct
2 Correct 2445 ms 3624 KB Output is correct
3 Correct 4057 ms 4928 KB Output is correct
4 Execution timed out 5058 ms 5468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 976 KB Output is correct
2 Correct 9 ms 1992 KB Output is correct
3 Correct 12 ms 2004 KB Output is correct
4 Correct 35 ms 2204 KB Output is correct
5 Correct 42 ms 4632 KB Output is correct
6 Correct 48 ms 4576 KB Output is correct
7 Execution timed out 5014 ms 4488 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3432 KB Output is correct
2 Correct 61 ms 3656 KB Output is correct
3 Correct 65 ms 2976 KB Output is correct
4 Correct 75 ms 2952 KB Output is correct
5 Correct 87 ms 5872 KB Output is correct
6 Correct 106 ms 5784 KB Output is correct
7 Correct 83 ms 5764 KB Output is correct
8 Correct 119 ms 5868 KB Output is correct
9 Correct 104 ms 5716 KB Output is correct
10 Correct 117 ms 5720 KB Output is correct
11 Correct 87 ms 5708 KB Output is correct
12 Correct 158 ms 5804 KB Output is correct