oj.uz

Submission #914511

# Submission time Handle Problem Language Result Execution time Memory
914511 2024-01-22T09:49:55 Z yellowtoad Sterilizing Spray (JOI15_sterilizing) C++17
5 / 100
 156 ms 4180 KB 
#include <iostream>
using namespace std;

long long n, test, k, a[100010], node[100010];

void build(int id, int x, int y) {
	if (x == y) {
		node[id] = a[x];
		return;
	}
	int mid = (x+y)/2;
	build(id*2,x,mid);
	build(id*2+1,mid+1,y);
	node[id] = node[id*2]+node[id*2+1];
}

void update(int id, int x, int y, int pos, int val) {
	if (x == y) {
		node[id] = val;
		return;
	}
	int mid = (x+y)/2;
	if (pos <= mid) update(id*2,x,mid,pos,val);
	else update(id*2+1,mid+1,y,pos,val);
	node[id] = node[id*2]+node[id*2+1];
}

void spray(int id, int x, int y, int l, int r) {
	if (node[id] == 0) return;
	if ((y < l) || (r < x)) return;
	if (x == y) {
		node[id] /= k;
		return;
	}
	int mid = (x+y)/2;
	spray(id*2,x,mid,l,r);
	spray(id*2+1,mid+1,y,l,r);
	node[id] = node[id*2]+node[id*2+1];
}

long long sum(int id, int x, int y, int l, int r) {
	if ((l <= x) && (y <= r)) return node[id];
	if ((y < l) || (r < x)) return 0;
	int mid = (x+y)/2;
	return sum(id*2,x,mid,l,r)+sum(id*2+1,mid+1,y,l,r);
}

int main() {
	cin >> n >> test >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build(1,1,n);
	while (test--) {
		int type, l, r;
		cin >> type >> l >> r;
		if (type == 1) update(1,1,n,l,r);
		if ((type == 2) && (k > 1)) spray(1,1,n,l,r);
		if (type == 3) cout << sum(1,1,n,l,r) << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 548 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 6 ms 612 KB Output is correct
9 Correct 8 ms 600 KB Output is correct
10 Correct 6 ms 756 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 5 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 3816 KB Output is correct
2 Correct 101 ms 3408 KB Output is correct
3 Runtime error 23 ms 4056 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 860 KB Output is correct
2 Correct 22 ms 1840 KB Output is correct
3 Correct 31 ms 1880 KB Output is correct
4 Correct 100 ms 2388 KB Output is correct
5 Runtime error 14 ms 3420 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 3156 KB Output is correct
2 Correct 127 ms 3452 KB Output is correct
3 Correct 110 ms 2696 KB Output is correct
4 Correct 156 ms 3228 KB Output is correct
5 Runtime error 29 ms 4180 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -