oj.uz

Submission #914512

# Submission time Handle Problem Language Result Execution time Memory
914512 2024-01-22T09:51:01 Z yellowtoad Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 242 ms 6720 KB 
#include <iostream>
using namespace std;

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

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 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 5 ms 428 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 5 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 3280 KB Output is correct
2 Correct 101 ms 3272 KB Output is correct
3 Correct 86 ms 4180 KB Output is correct
4 Correct 109 ms 5720 KB Output is correct
5 Correct 155 ms 6272 KB Output is correct
6 Correct 132 ms 6224 KB Output is correct
7 Correct 133 ms 6228 KB Output is correct
8 Correct 139 ms 6720 KB Output is correct
9 Correct 128 ms 6228 KB Output is correct
10 Correct 127 ms 6228 KB Output is correct
11 Correct 143 ms 6224 KB Output is correct
12 Correct 126 ms 6224 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 856 KB Output is correct
2 Correct 23 ms 2904 KB Output is correct
3 Correct 32 ms 3156 KB Output is correct
4 Correct 100 ms 2904 KB Output is correct
5 Correct 115 ms 4432 KB Output is correct
6 Correct 117 ms 4724 KB Output is correct
7 Correct 108 ms 4948 KB Output is correct
8 Correct 116 ms 4920 KB Output is correct
9 Correct 109 ms 4744 KB Output is correct
10 Correct 109 ms 4688 KB Output is correct
11 Correct 121 ms 4588 KB Output is correct
12 Correct 111 ms 4692 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 3152 KB Output is correct
2 Correct 126 ms 3276 KB Output is correct
3 Correct 116 ms 3156 KB Output is correct
4 Correct 149 ms 3156 KB Output is correct
5 Correct 174 ms 4988 KB Output is correct
6 Correct 208 ms 5996 KB Output is correct
7 Correct 200 ms 5960 KB Output is correct
8 Correct 205 ms 6108 KB Output is correct
9 Correct 200 ms 6036 KB Output is correct
10 Correct 203 ms 5968 KB Output is correct
11 Correct 174 ms 5992 KB Output is correct
12 Correct 242 ms 6000 KB Output is correct