oj.uz

Submission #468432

# Submission time Handle Problem Language Result Execution time Memory
468432 2021-08-28T08:07:42 Z stefantaga Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 299 ms 6156 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int N = 1e5 + 5;
int seg[N * 4];
int a[N], n, q, k;
 
void Build(int l, int r, int pos) {
	if(l == r) {
		seg[pos] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	Build(l, mid, pos * 2);
	Build(mid + 1, r, pos * 2 + 1);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}
 
void Update(int l, int r, int pos, int qidx, int qval) {
	if(l == r) {
		seg[pos] = qval;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= qidx) {
		Update(l, mid, pos * 2, qidx, qval);
	}
	else {
		Update(mid + 1, r, pos * 2 + 1, qidx, qval);
	}
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}
 
void Spray(int l, int r, int pos, int ql, int qr) {
	if(l > qr || ql > r || seg[pos] == 0)
		return;
	if(l == r) {
		seg[pos] /= k;
		return;
	}
	int mid = (l + r) >> 1;
	Spray(l, mid, pos * 2, ql, qr);
	Spray(mid + 1, r, pos * 2 + 1, ql, qr);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}
 
int Query(int l, int r, int pos, int ql, int qr) {
	if(l > qr || ql > r)
		return 0;
	if(ql <= l && r <= qr) {
		return seg[pos];
	}
	int mid = (l + r) >> 1;
	return Query(l, mid, pos * 2, ql, qr) + Query(mid + 1, r, pos * 2 + 1, ql, qr);
}
 
void Solve() {
	cin >> n >> q >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	Build(1, n, 1);
	for(int i = 1; i <= q; i++) {
		int command;
		cin >> command;
		if(command == 1) {
			int idx, val;
			cin >> idx >> val;
			Update(1, n, 1, idx, val);
		}
		else if(command == 2) {
			int ql, qr;
			cin >> ql >> qr;
			if(k != 1) {
				Spray(1, n, 1, ql, qr);
			}
		}
		else {
			int ql, qr;
			cin >> ql >> qr;
			cout << Query(1, n, 1, ql, qr) << "\n";
		}
	}
}
 
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Solve();
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 328 KB Output is correct
5 Correct 4 ms 388 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 4 ms 460 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 4 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4036 KB Output is correct
2 Correct 48 ms 3524 KB Output is correct
3 Correct 44 ms 4932 KB Output is correct
4 Correct 54 ms 5564 KB Output is correct
5 Correct 64 ms 5948 KB Output is correct
6 Correct 69 ms 6156 KB Output is correct
7 Correct 67 ms 5956 KB Output is correct
8 Correct 66 ms 5976 KB Output is correct
9 Correct 66 ms 5824 KB Output is correct
10 Correct 62 ms 5940 KB Output is correct
11 Correct 63 ms 5828 KB Output is correct
12 Correct 65 ms 5876 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 972 KB Output is correct
2 Correct 17 ms 1992 KB Output is correct
3 Correct 19 ms 2108 KB Output is correct
4 Correct 53 ms 2192 KB Output is correct
5 Correct 68 ms 4580 KB Output is correct
6 Correct 75 ms 4704 KB Output is correct
7 Correct 56 ms 4704 KB Output is correct
8 Correct 67 ms 4548 KB Output is correct
9 Correct 66 ms 4432 KB Output is correct
10 Correct 61 ms 4416 KB Output is correct
11 Correct 63 ms 4548 KB Output is correct
12 Correct 62 ms 4420 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 3400 KB Output is correct
2 Correct 106 ms 3764 KB Output is correct
3 Correct 117 ms 2948 KB Output is correct
4 Correct 133 ms 3040 KB Output is correct
5 Correct 166 ms 5828 KB Output is correct
6 Correct 173 ms 5800 KB Output is correct
7 Correct 144 ms 5824 KB Output is correct
8 Correct 228 ms 5812 KB Output is correct
9 Correct 193 ms 5880 KB Output is correct
10 Correct 230 ms 5760 KB Output is correct
11 Correct 165 ms 5740 KB Output is correct
12 Correct 299 ms 5764 KB Output is correct