oj.uz

Submission #503377

# Submission time Handle Problem Language Result Execution time Memory
503377 2022-01-07T18:34:33 Z desmond_willow Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 364 ms 6452 KB 
#include<bits/stdc++.h>

using namespace std;

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

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

void build (int l, int r, int pos) {
	if (l == r) {
		maxtree[pos] = arr[l];
		sumtree[pos] = arr[l];
		return;
	}
	int mid = (l + r)/2;
	build (l, mid, pos * 2);
	build (mid + 1, r, pos * 2 + 1);
	maxtree[pos] = max (maxtree[pos * 2], maxtree[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;
		maxtree[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];
	maxtree[pos] = max(maxtree[pos * 2], maxtree[pos * 2 + 1]);
}

void spray (int l, int r, int target_l, int target_r, int pos) {
	if (r < target_l || l > target_r || maxtree[pos] == 0) {return;}
	
	if (l == r) {
		maxtree[pos] = maxtree[pos] / k;
		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];
	maxtree[pos] = max(maxtree[pos * 2], maxtree[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 4 ms 308 KB Output is correct
2 Incorrect 2 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 992 KB Output is correct
2 Correct 26 ms 2268 KB Output is correct
3 Correct 40 ms 2348 KB Output is correct
4 Correct 117 ms 2340 KB Output is correct
5 Correct 143 ms 5196 KB Output is correct
6 Correct 144 ms 5212 KB Output is correct
7 Incorrect 85 ms 4948 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 146 ms 3716 KB Output is correct
2 Correct 224 ms 3832 KB Output is correct
3 Correct 153 ms 3272 KB Output is correct
4 Correct 192 ms 3048 KB Output is correct
5 Correct 245 ms 6396 KB Output is correct
6 Correct 257 ms 6452 KB Output is correct
7 Correct 256 ms 6436 KB Output is correct
8 Correct 287 ms 6412 KB Output is correct
9 Correct 288 ms 6348 KB Output is correct
10 Correct 295 ms 6376 KB Output is correct
11 Correct 257 ms 6352 KB Output is correct
12 Correct 364 ms 6376 KB Output is correct