oj.uz

Submission #503393

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

using namespace std;

const int MAX_N = 16 * (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, long long 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; long long int 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 4 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 91 ms 1688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 480 KB Output is correct
2 Correct 25 ms 1500 KB Output is correct
3 Correct 38 ms 1528 KB Output is correct
4 Correct 135 ms 1052 KB Output is correct
5 Correct 134 ms 2756 KB Output is correct
6 Correct 133 ms 2764 KB Output is correct
7 Incorrect 83 ms 2832 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 141 ms 1712 KB Output is correct
2 Correct 180 ms 1696 KB Output is correct
3 Correct 144 ms 1608 KB Output is correct
4 Correct 192 ms 1092 KB Output is correct
5 Correct 253 ms 2988 KB Output is correct
6 Correct 239 ms 2996 KB Output is correct
7 Correct 225 ms 2904 KB Output is correct
8 Correct 274 ms 3032 KB Output is correct
9 Correct 239 ms 2952 KB Output is correct
10 Correct 266 ms 2968 KB Output is correct
11 Correct 224 ms 3016 KB Output is correct
12 Correct 324 ms 3052 KB Output is correct