oj.uz

Submission #412416

# Submission time Handle Problem Language Result Execution time Memory
412416 2021-05-26T20:28:14 Z aryan12 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 301 ms 5968 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 5 ms 336 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 420 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 8 ms 420 KB Output is correct
8 Correct 9 ms 420 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2140 KB Output is correct
2 Correct 50 ms 1932 KB Output is correct
3 Correct 45 ms 3192 KB Output is correct
4 Correct 56 ms 3416 KB Output is correct
5 Correct 66 ms 3572 KB Output is correct
6 Correct 82 ms 3524 KB Output is correct
7 Correct 65 ms 3512 KB Output is correct
8 Correct 65 ms 3572 KB Output is correct
9 Correct 103 ms 3576 KB Output is correct
10 Correct 72 ms 3624 KB Output is correct
11 Correct 62 ms 3620 KB Output is correct
12 Correct 105 ms 3628 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 520 KB Output is correct
2 Correct 14 ms 1716 KB Output is correct
3 Correct 29 ms 1700 KB Output is correct
4 Correct 51 ms 1056 KB Output is correct
5 Correct 72 ms 3612 KB Output is correct
6 Correct 66 ms 4628 KB Output is correct
7 Correct 74 ms 4736 KB Output is correct
8 Correct 70 ms 4576 KB Output is correct
9 Correct 61 ms 4464 KB Output is correct
10 Correct 63 ms 4428 KB Output is correct
11 Correct 172 ms 4468 KB Output is correct
12 Correct 171 ms 4428 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1912 KB Output is correct
2 Correct 108 ms 1964 KB Output is correct
3 Correct 118 ms 1728 KB Output is correct
4 Correct 131 ms 1348 KB Output is correct
5 Correct 174 ms 3880 KB Output is correct
6 Correct 199 ms 5968 KB Output is correct
7 Correct 185 ms 5828 KB Output is correct
8 Correct 208 ms 5828 KB Output is correct
9 Correct 200 ms 5792 KB Output is correct
10 Correct 226 ms 5732 KB Output is correct
11 Correct 163 ms 5708 KB Output is correct
12 Correct 301 ms 5700 KB Output is correct