oj.uz

Submission #503391

# Submission time Handle Problem Language Result Execution time Memory
503391 2022-01-07T19:20:42 Z desmond_willow Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 326 ms 3108 KB 
#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 8 * (100069);
int n, q, k;

long long int sumtree[MAX_N];
int arr[MAX_N];

void build (int l, int r, int pos) {
	if (l == r) {
		sumtree[pos] = arr[l];
		return;
	}
	int mid = (l + r)/2;
	build (l, mid, pos * 2);
	build (mid + 1, r, pos * 2 + 1);
	sumtree[pos] = sumtree[pos * 2] + sumtree[pos * 2 + 1];
}

void update (int l, int r, int pos, int index, int value) {
	if (l == r) {
		sumtree[pos] = value;
		return;
	}
	
	int mid = (l + r)/2;
	if (index <= mid) {
		update (l, mid, pos * 2, index, value);
	} else {
		update (mid + 1, r, pos * 2 + 1, index, value);
	}
	sumtree[pos] = sumtree[pos * 2] + sumtree[pos * 2 + 1];
}

void spray (int l, int r, int target_l, int target_r, int pos) {
	if (r < target_l || l > target_r || sumtree[pos] == 0) {return;}
	
	if (l == r) {
		sumtree[pos] = sumtree[pos] / k;
		return;
	}

	int mid = (l + r)/2;
	spray (l, mid, target_l, target_r, pos * 2);
	spray (mid + 1, r, target_l, target_r, pos * 2 + 1);

	sumtree[pos] = sumtree[pos * 2] + sumtree[pos * 2 + 1];
}

long long int query (int l, int r, int target_l, int target_r, int pos) {
	if (r < target_l || l > target_r) {return 0;}
	if (target_l <= l && r <= target_r) {return sumtree[pos];}

	int mid = (l + r)/2;
	return query(l, mid, target_l, target_r, pos*2) + 
		query(mid + 1, r, target_l, target_r, pos*2 + 1);
}

int main () {
	cin >> n >> q >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	build (1, n, 1);

	for (int i = 0; i < q; i++) {
		int op_type; cin >> op_type;
		if (op_type == 1) {
			int ind, val; cin >> ind >> val;
			update (1, n, 1, ind, val);
		} else if (op_type == 2 && k > 1) {
			int l, r; cin >> l >> r;
			spray (1, n, l, r, 1);
		} else if (op_type == 3) {
			int l, r; cin >> l >> r;
			cout << query(1, n, l, r, 1) << endl;
		}
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 1676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 464 KB Output is correct
2 Correct 26 ms 1520 KB Output is correct
3 Correct 39 ms 1524 KB Output is correct
4 Correct 121 ms 928 KB Output is correct
5 Correct 161 ms 2696 KB Output is correct
6 Correct 133 ms 2732 KB Output is correct
7 Incorrect 90 ms 2792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 1604 KB Output is correct
2 Correct 165 ms 1688 KB Output is correct
3 Correct 138 ms 1604 KB Output is correct
4 Correct 191 ms 1244 KB Output is correct
5 Correct 225 ms 3000 KB Output is correct
6 Correct 232 ms 2952 KB Output is correct
7 Correct 228 ms 2892 KB Output is correct
8 Correct 265 ms 3044 KB Output is correct
9 Correct 246 ms 2992 KB Output is correct
10 Correct 268 ms 3108 KB Output is correct
11 Correct 227 ms 3012 KB Output is correct
12 Correct 326 ms 3012 KB Output is correct